oj.uz

Submission #383921

# Submission time Handle Problem Language Result Execution time Memory
383921 2021-03-31T02:30:33 Z nikatamliani Examination (JOI19_examination) C++14
100 / 100
 806 ms 59036 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
template <typename T>
struct fenwick_tree {
    int size;
    vector<T> tree;
    T neutral;
    fenwick_tree(int n, T _neutral) {
        size = n;
        neutral = _neutral;
        tree = vector<T>(n + 1);
    }

    void update(int index, T value) {
        for(; index <= size; index += index & -index) {
            tree[index] += value;
        }
    }
    T query_prefix(int index) {
        T ans = neutral;
        for(; index; index -= index & -index) {
            ans += tree[index];
        }
        return ans; 
    }
    T query(int l, int r) {
        return query_prefix(r) - query_prefix(l - 1);
    }
};
map<int, int> compress(vector<int> &coords) {
	sort(coords.begin(), coords.end());
	map<int, int> compressed;
	for(int i = 0, current = 0; i < (int)coords.size(); ++i) {
		if(i == 0 || coords[i] != coords[i - 1]) ++current;
		compressed[coords[i]] = current;
	}
	return compressed;
}
int x[N], y[N], a[N], b[N], c[N];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m; 
	vector<vector<int>> v;
	vector<int> sorted_sums;
	for(int i = 1; i <= n; ++i) {
		cin >> x[i] >> y[i];
		sorted_sums.push_back(x[i] + y[i]);
		v.push_back({x[i], y[i]});
	}
	sort(sorted_sums.begin(), sorted_sums.end());
	sort(v.begin(), v.end());
	for(int i = 1; i <= n; ++i) {
		x[i] = v[i - 1][0];
		y[i] = v[i - 1][1];
	}
	v.clear();
	for(int i = 1; i <= m; ++i) {
		cin >> a[i] >> b[i] >> c[i];
	}
	vector<int> type1, type2;
	for(int i = 1; i <= m; ++i) {
		if(a[i] + b[i] >= c[i]) {
			type1.push_back(i);
		} else {
			type2.push_back(i);
		}
	}
	map<int, int> compressed_sum, compressed_x, compressed_y;
	//sum
	vector<int> coords(n + m); 
	for(int i = 1; i <= m; ++i) {
		coords[i - 1] = c[i];
	}
	for(int i = 1; i <= n; ++i) {
		coords[i + m - 1] = x[i] + y[i];
	}
	compressed_sum = compress(coords);
	//x
	for(int i = 1; i <= m; ++i) {
		coords[i - 1] = a[i];
	}
	for(int i = 1; i <= n; ++i) {
		coords[i + m - 1] = x[i];
	}
	compressed_x = compress(coords);
	//y
	for(int i = 1; i <= m; ++i) {
		coords[i - 1] = b[i];
	}
	for(int i = 1; i <= n; ++i) {
		coords[i + m - 1] = y[i];
	}
	compressed_y = compress(coords);
	sort(type1.begin(), type1.end(), [&](int x, int y) {
		if(a[x] == a[y]) {
			if(b[x] == b[y]) {
				return c[x] < c[y];
			}
			return b[x] < b[y];
		}
		return a[x] < a[y];
	});
	auto sum = [](int x, int y) -> int {
		return x + y;
	};
	fenwick_tree<int> t(N, 0);
	fenwick_tree<int> tx(N, 0);
	fenwick_tree<int> ty(N, 0);
	vector<int> ans(m+1);
	for(int i = (int)type1.size() - 1, j = n; i >= 0; --i) {
		int q_id = type1[i];
		while(j > 0 && x[j] >= a[q_id]) {
			int val = compressed_y[y[j]];
			t.update(val, 1);
			--j;
		}
		int val = compressed_y[b[q_id]];
		ans[q_id] = t.query(val, t.size);
	}
	for(int i : type2) {
		int l = 0, r = n - 1, ind = n;
		while(r >= l) {
			int middle = l + r >> 1;
			if(sorted_sums[middle] >= c[i]) {
				r = middle - 1;
				ind = middle;
			} else {
				l = middle + 1;
			}
		}
		ans[i] = n - ind;
	}
	vector<int> sums[N], queries[N];
	for(int i = 1; i <= n; ++i) {
		int val = compressed_sum[x[i] + y[i]];
		sums[val].push_back(i);
	}
	for(int i : type2) {
		if(i == -1) continue;
		int val = compressed_sum[c[i]];
		queries[val].push_back(i);
	}
	int max_sum_val = (int)compressed_sum.size();
	for(int i = max_sum_val; i >= 1; --i) {
		for(int id : sums[i]) {
			int val_x = compressed_x[x[id]];
			int val_y = compressed_y[y[id]];
			tx.update(val_x, 1); 
			ty.update(val_y, 1);
		}
		for(int id : queries[i]) {
			int val_x = compressed_x[a[id]];
			int val_y = compressed_y[b[id]];
			ans[id] -= tx.query(1, val_x - 1);
			ans[id] -= ty.query(1, val_y - 1);
		}
	}
	for(int i = 1; i <= m; ++i) {
		cout << ans[i] << '\n';
	}
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:125:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |    int middle = l + r >> 1;
      |                 ~~^~~
examination.cpp:105:7: warning: variable 'sum' set but not used [-Wunused-but-set-variable]
  105 |  auto sum = [](int x, int y) -> int {
      |       ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 18048 KB Output is correct
2 Correct 12 ms 18028 KB Output is correct
3 Correct 12 ms 18028 KB Output is correct
4 Correct 12 ms 18028 KB Output is correct
5 Correct 12 ms 18028 KB Output is correct
6 Correct 12 ms 18028 KB Output is correct
7 Correct 24 ms 19180 KB Output is correct
8 Correct 23 ms 19180 KB Output is correct
9 Correct 23 ms 19180 KB Output is correct
10 Correct 19 ms 18924 KB Output is correct
11 Correct 20 ms 18924 KB Output is correct
12 Correct 15 ms 18284 KB Output is correct
13 Correct 21 ms 19052 KB Output is correct
14 Correct 21 ms 18924 KB Output is correct
15 Correct 21 ms 18924 KB Output is correct
16 Correct 18 ms 18668 KB Output is correct
17 Correct 21 ms 19052 KB Output is correct
18 Correct 14 ms 18284 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 38812 KB Output is correct
2 Correct 478 ms 38812 KB Output is correct
3 Correct 450 ms 39068 KB Output is correct
4 Correct 230 ms 33948 KB Output is correct
5 Correct 272 ms 34168 KB Output is correct
6 Correct 138 ms 26908 KB Output is correct
7 Correct 427 ms 38044 KB Output is correct
8 Correct 435 ms 38048 KB Output is correct
9 Correct 394 ms 37220 KB Output is correct
10 Correct 238 ms 33820 KB Output is correct
11 Correct 218 ms 33948 KB Output is correct
12 Correct 121 ms 26012 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 38812 KB Output is correct
2 Correct 478 ms 38812 KB Output is correct
3 Correct 450 ms 39068 KB Output is correct
4 Correct 230 ms 33948 KB Output is correct
5 Correct 272 ms 34168 KB Output is correct
6 Correct 138 ms 26908 KB Output is correct
7 Correct 427 ms 38044 KB Output is correct
8 Correct 435 ms 38048 KB Output is correct
9 Correct 394 ms 37220 KB Output is correct
10 Correct 238 ms 33820 KB Output is correct
11 Correct 218 ms 33948 KB Output is correct
12 Correct 121 ms 26012 KB Output is correct
13 Correct 589 ms 42652 KB Output is correct
14 Correct 513 ms 41372 KB Output is correct
15 Correct 479 ms 38812 KB Output is correct
16 Correct 307 ms 36252 KB Output is correct
17 Correct 340 ms 36252 KB Output is correct
18 Correct 138 ms 26140 KB Output is correct
19 Correct 590 ms 42592 KB Output is correct
20 Correct 548 ms 41884 KB Output is correct
21 Correct 606 ms 42524 KB Output is correct
22 Correct 240 ms 33776 KB Output is correct
23 Correct 217 ms 33820 KB Output is correct
24 Correct 116 ms 26012 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 18048 KB Output is correct
2 Correct 12 ms 18028 KB Output is correct
3 Correct 12 ms 18028 KB Output is correct
4 Correct 12 ms 18028 KB Output is correct
5 Correct 12 ms 18028 KB Output is correct
6 Correct 12 ms 18028 KB Output is correct
7 Correct 24 ms 19180 KB Output is correct
8 Correct 23 ms 19180 KB Output is correct
9 Correct 23 ms 19180 KB Output is correct
10 Correct 19 ms 18924 KB Output is correct
11 Correct 20 ms 18924 KB Output is correct
12 Correct 15 ms 18284 KB Output is correct
13 Correct 21 ms 19052 KB Output is correct
14 Correct 21 ms 18924 KB Output is correct
15 Correct 21 ms 18924 KB Output is correct
16 Correct 18 ms 18668 KB Output is correct
17 Correct 21 ms 19052 KB Output is correct
18 Correct 14 ms 18284 KB Output is correct
19 Correct 465 ms 38812 KB Output is correct
20 Correct 478 ms 38812 KB Output is correct
21 Correct 450 ms 39068 KB Output is correct
22 Correct 230 ms 33948 KB Output is correct
23 Correct 272 ms 34168 KB Output is correct
24 Correct 138 ms 26908 KB Output is correct
25 Correct 427 ms 38044 KB Output is correct
26 Correct 435 ms 38048 KB Output is correct
27 Correct 394 ms 37220 KB Output is correct
28 Correct 238 ms 33820 KB Output is correct
29 Correct 218 ms 33948 KB Output is correct
30 Correct 121 ms 26012 KB Output is correct
31 Correct 589 ms 42652 KB Output is correct
32 Correct 513 ms 41372 KB Output is correct
33 Correct 479 ms 38812 KB Output is correct
34 Correct 307 ms 36252 KB Output is correct
35 Correct 340 ms 36252 KB Output is correct
36 Correct 138 ms 26140 KB Output is correct
37 Correct 590 ms 42592 KB Output is correct
38 Correct 548 ms 41884 KB Output is correct
39 Correct 606 ms 42524 KB Output is correct
40 Correct 240 ms 33776 KB Output is correct
41 Correct 217 ms 33820 KB Output is correct
42 Correct 116 ms 26012 KB Output is correct
43 Correct 768 ms 57824 KB Output is correct
44 Correct 789 ms 57756 KB Output is correct
45 Correct 703 ms 57036 KB Output is correct
46 Correct 382 ms 48596 KB Output is correct
47 Correct 468 ms 48412 KB Output is correct
48 Correct 147 ms 27024 KB Output is correct
49 Correct 721 ms 57756 KB Output is correct
50 Correct 806 ms 58508 KB Output is correct
51 Correct 781 ms 59036 KB Output is correct
52 Correct 395 ms 48284 KB Output is correct
53 Correct 253 ms 42012 KB Output is correct