Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- #include <map>
- #include <algorithm>
- #include <vector>
- using namespace std;
- const long long max_statues = 1e5 + 10;
- const long long max_rect = 3e4 + 10;
- const long long max_segment_tree = 130001;
- struct statue {
- long long x, y, v;
- statue() {}
- statue(long long _x, long long _y, long long _v) {
- x = _x;
- y = _y;
- v = _v;
- }
- };
- struct rect {
- long long x1, x2, y1, y2;
- rect () {}
- rect(long long _x1, long long _y1, long long _x2, long long _y2) {
- x1 = _x1;
- x2 = _x2;
- y1 = _y1;
- y2 = _y2;
- }
- };
- struct event {
- long long type; // statues, left edge of rect, right edge of rect
- long long x, y, v;
- long long y1, y2;
- long long at;
- event() {}
- event(long long _type, long long _x, long long _y, long long _v, long long _y1, long long _y2, long long _at) {
- type = _type;
- x = _x;
- y = _y;
- v = _v;
- y1 = _y1;
- y2 = _y2;
- at = _at;
- }
- bool operator < (const event &tmp) const {
- if(x == tmp.x) {
- return type < tmp.type;
- }
- return x < tmp.x;
- }
- };
- statue statues[max_statues];
- rect rects[max_rect];
- long long n, k;
- void compress_vertically() {
- set<long long> st;
- for(long long i = 0; i < n; i++) {
- st.insert(statues[i].y);
- }
- for(long long i = 0; i < k; i++) {
- st.insert(rects[i].y1);
- st.insert(rects[i].y2);
- }
- long long value = 0;
- map<long long, long long> compressed_values;
- for(long long x : st) {
- if(compressed_values.find(x) == compressed_values.end()) {
- compressed_values[x] = value;
- value++;
- }
- }
- for(long long i = 0; i < n; i++) {
- statues[i].y = compressed_values[statues[i].y];
- }
- for(long long i = 0; i < k; i++) {
- rects[i].y1 = compressed_values[rects[i].y1];
- rects[i].y2 = compressed_values[rects[i].y2];
- }
- }
- long long segment_tree[max_segment_tree * 3];
- void build(long long L, long long R, long long node) {
- if(L == R) {
- segment_tree[node] = 0;
- }
- else {
- long long mid = (L + R) / 2;
- build(L, mid, 2 * node);
- build(mid + 1, R, 2 * node + 1);
- segment_tree[node] = segment_tree[2 * node] + segment_tree[2 * node + 1];
- }
- }
- void update(long long L, long long R, long long node, long long idx, long long value) {
- if(L == R) {
- segment_tree[node] += value;
- return;
- }
- long long mid = (L + R) / 2;
- if(idx <= mid) {
- update(L, mid, 2 * node, idx, value);
- }
- else {
- update(mid + 1, R, 2 * node + 1, idx, value);
- }
- segment_tree[node] = segment_tree[2 * node] + segment_tree[2 * node + 1];
- }
- long long query(long long i, long long j, long long L, long long R, long long node) {
- // L R i L R j L R
- if(i <= L and R <= j) {
- return segment_tree[node];
- }
- if(R < i or j < L){
- return 0;
- }
- long long mid = (L + R) / 2;
- return query(i, j, L, mid, 2 * node) + query(i, j, mid + 1, R, 2 * node + 1);
- }
- long long sum_till_left_edge[max_statues];
- long long result[max_statues];
- int main() {
- ios_base::sync_with_stdio(false);
- cin >> n;
- for(long long i = 0; i < n; i++) {
- cin >> statues[i].x >> statues[i].y >> statues[i].v;
- }
- cin >> k;
- for(long long i = 0; i < k; i++) {
- cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2;
- }
- compress_vertically();
- vector<event> queries;
- for(long long i = 0; i < n; i++) {
- event e(1, statues[i].x, statues[i].y, statues[i].v, 0, 0, i);
- queries.push_back(e);
- }
- for(long long i = 0; i < k; i++) {
- event l(0, rects[i].x1, 0, 0, rects[i].y1, rects[i].y2, i);
- event r(2, rects[i].x2, 0, 0, rects[i].y1, rects[i].y2, i);
- queries.push_back(l);
- queries.push_back(r);
- }
- sort(queries.begin(), queries.end());
- build(0, max_segment_tree, 1);
- for(long long i = 0; i < (long long) queries.size(); i++) {
- if(queries[i].type == 1) {
- update(0, max_segment_tree, 1, queries[i].y, queries[i].v);
- }
- if(queries[i].type == 0) {
- sum_till_left_edge[queries[i].at] = query(queries[i].y1, queries[i].y2, 0, max_segment_tree, 1);
- }
- if(queries[i].type == 2) {
- result[queries[i].at] = query(queries[i].y1, queries[i].y2, 0, max_segment_tree, 1) - sum_till_left_edge[queries[i].at];
- }
- }
- for(long long i = 0; i < k; i++) {
- cout << result[i] << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement