oj.uz

Submission #383923

# Submission time Handle Problem Language Result Execution time Memory
383923 2021-03-31T02:31:52 Z nikatamliani Examination (JOI19_examination) C++14
100 / 100
 860 ms 53148 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+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 8 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Correct 9 ms 12140 KB Output is correct
5 Correct 9 ms 12140 KB Output is correct
6 Correct 9 ms 12140 KB Output is correct
7 Correct 20 ms 13292 KB Output is correct
8 Correct 20 ms 13292 KB Output is correct
9 Correct 21 ms 13292 KB Output is correct
10 Correct 17 ms 13036 KB Output is correct
11 Correct 17 ms 13036 KB Output is correct
12 Correct 13 ms 12396 KB Output is correct
13 Correct 18 ms 13164 KB Output is correct
14 Correct 18 ms 13164 KB Output is correct
15 Correct 18 ms 13164 KB Output is correct
16 Correct 15 ms 12780 KB Output is correct
17 Correct 17 ms 13036 KB Output is correct
18 Correct 12 ms 12396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 33052 KB Output is correct
2 Correct 451 ms 33076 KB Output is correct
3 Correct 453 ms 32924 KB Output is correct
4 Correct 251 ms 28060 KB Output is correct
5 Correct 264 ms 28060 KB Output is correct
6 Correct 130 ms 21020 KB Output is correct
7 Correct 439 ms 32028 KB Output is correct
8 Correct 439 ms 32156 KB Output is correct
9 Correct 415 ms 31260 KB Output is correct
10 Correct 234 ms 27932 KB Output is correct
11 Correct 214 ms 27932 KB Output is correct
12 Correct 112 ms 20124 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 33052 KB Output is correct
2 Correct 451 ms 33076 KB Output is correct
3 Correct 453 ms 32924 KB Output is correct
4 Correct 251 ms 28060 KB Output is correct
5 Correct 264 ms 28060 KB Output is correct
6 Correct 130 ms 21020 KB Output is correct
7 Correct 439 ms 32028 KB Output is correct
8 Correct 439 ms 32156 KB Output is correct
9 Correct 415 ms 31260 KB Output is correct
10 Correct 234 ms 27932 KB Output is correct
11 Correct 214 ms 27932 KB Output is correct
12 Correct 112 ms 20124 KB Output is correct
13 Correct 567 ms 36636 KB Output is correct
14 Correct 552 ms 35484 KB Output is correct
15 Correct 490 ms 32924 KB Output is correct
16 Correct 297 ms 30364 KB Output is correct
17 Correct 333 ms 30364 KB Output is correct
18 Correct 140 ms 20272 KB Output is correct
19 Correct 596 ms 36664 KB Output is correct
20 Correct 533 ms 35868 KB Output is correct
21 Correct 633 ms 36636 KB Output is correct
22 Correct 236 ms 27932 KB Output is correct
23 Correct 210 ms 27932 KB Output is correct
24 Correct 107 ms 20124 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Correct 9 ms 12140 KB Output is correct
5 Correct 9 ms 12140 KB Output is correct
6 Correct 9 ms 12140 KB Output is correct
7 Correct 20 ms 13292 KB Output is correct
8 Correct 20 ms 13292 KB Output is correct
9 Correct 21 ms 13292 KB Output is correct
10 Correct 17 ms 13036 KB Output is correct
11 Correct 17 ms 13036 KB Output is correct
12 Correct 13 ms 12396 KB Output is correct
13 Correct 18 ms 13164 KB Output is correct
14 Correct 18 ms 13164 KB Output is correct
15 Correct 18 ms 13164 KB Output is correct
16 Correct 15 ms 12780 KB Output is correct
17 Correct 17 ms 13036 KB Output is correct
18 Correct 12 ms 12396 KB Output is correct
19 Correct 450 ms 33052 KB Output is correct
20 Correct 451 ms 33076 KB Output is correct
21 Correct 453 ms 32924 KB Output is correct
22 Correct 251 ms 28060 KB Output is correct
23 Correct 264 ms 28060 KB Output is correct
24 Correct 130 ms 21020 KB Output is correct
25 Correct 439 ms 32028 KB Output is correct
26 Correct 439 ms 32156 KB Output is correct
27 Correct 415 ms 31260 KB Output is correct
28 Correct 234 ms 27932 KB Output is correct
29 Correct 214 ms 27932 KB Output is correct
30 Correct 112 ms 20124 KB Output is correct
31 Correct 567 ms 36636 KB Output is correct
32 Correct 552 ms 35484 KB Output is correct
33 Correct 490 ms 32924 KB Output is correct
34 Correct 297 ms 30364 KB Output is correct
35 Correct 333 ms 30364 KB Output is correct
36 Correct 140 ms 20272 KB Output is correct
37 Correct 596 ms 36664 KB Output is correct
38 Correct 533 ms 35868 KB Output is correct
39 Correct 633 ms 36636 KB Output is correct
40 Correct 236 ms 27932 KB Output is correct
41 Correct 210 ms 27932 KB Output is correct
42 Correct 107 ms 20124 KB Output is correct
43 Correct 769 ms 52252 KB Output is correct
44 Correct 768 ms 51996 KB Output is correct
45 Correct 727 ms 51100 KB Output is correct
46 Correct 388 ms 42652 KB Output is correct
47 Correct 481 ms 42652 KB Output is correct
48 Correct 139 ms 20892 KB Output is correct
49 Correct 710 ms 51868 KB Output is correct
50 Correct 860 ms 52636 KB Output is correct
51 Correct 813 ms 53148 KB Output is correct
52 Correct 378 ms 42396 KB Output is correct
53 Correct 241 ms 36252 KB Output is correct