oj.uz

Submission #383918

# Submission time Handle Problem Language Result Execution time Memory
383918 2021-03-31T02:11:55 Z nikatamliani Examination (JOI19_examination) C++14
100 / 100
 1121 ms 70428 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
template <typename T>
struct segment_tree {
	vector<T> tree;
	T neutral;
	int size;
	function<T(T, T)> join;
	segment_tree(int _size, T _neutral, function<T(T, T)> f) {
		join = f;
		size = _size;
		tree = vector<T>(4 * size);
		neutral = _neutral;
	}
	
	void point_update(int id, T val) {
		point_update(1, size, id, val, 1); 
	}
	
	void point_update(int l, int r, int x, T val, int p) {
		if(l > x || r < x) {
			return;
		}
		if(l == r) {
			tree[p] = val;
			return;
		}
		int middle = l + r >> 1;
		point_update(l, middle, x, val, p << 1);
		point_update(middle+1, r, x, val, p << 1 | 1);
		tree[p] = join(tree[p << 1], tree[p << 1 | 1]);
	}
	
	T get(int id) {
		return query(id, id);
	}
	
	T query(int L, int R) {
		return query(1, size, L, R, 1); 
	}
	
	T query(int l, int r, int L, int R, int p) {
		if(L > r || l > R) return neutral;
		if(L <= l && R >= r) return tree[p];
		int middle = l + r >> 1;
		T lft = query(l, middle, L, R, p << 1);
		T rgh = query(middle+1, r, L, R, p << 1 | 1);
		return join(lft, rgh);
	}
};
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;
	};
	segment_tree<int> t(N, 0, sum);
	segment_tree<int> tx(N, 0, sum);
	segment_tree<int> ty(N, 0, sum);
	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.point_update(val, t.get(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;
			}
		}
//		all[i] = n - ind;
		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.point_update(val_x, tx.get(val_x)+1); 
			ty.point_update(val_y, ty.get(val_y)+1);
		}
		for(int id : queries[i]) {
			int val_x = compressed_x[a[id]];
			int val_y = compressed_y[b[id]];
			/* sumA[id] */ ans[id] -= tx.query(1, val_x - 1);
			/* sumB[id] */ ans[id] -= ty.query(1, val_y - 1);
		}
	}
	for(int i = 1; i <= m; ++i) {
		cout << ans[i] << '\n';
	}
//	for (int i = 1; i <= m; ++i) {
//		if (a[i] + b[i] >= c[i]) {
//			int ans = 0;
//			for(int j = 1; j <= n; ++j) {
//				if (x[j] >= a[i] && y[j] >= b[i]) {
//					++ans;
//				}
//			}
//			cout << ans << '\n';
//			continue;
//		}
//		int all = 0, sumA = 0, sumB = 0;
//		for (int j = 1; j <= n; ++j) {
//			if (x[j] + y[j] >= c[i]) {
//				++all;
//			}
//			if (x[j] < a[i] && x[j] + y[j] >= c[i]) {
//				++sumA;
//			}
//			if (y[j] < b[i] && x[j] + y[j] >= c[i]) {
//				++sumB;
//			}
//		}
//		cout << all - sumA - sumB << '\n';
//	}
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:146:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  146 |    int middle = l + r >> 1;
      |                 ~~^~~
examination.cpp: In instantiation of 'void segment_tree<T>::point_update(int, int, int, T, int) [with T = int]':
examination.cpp:18:3:   required from 'void segment_tree<T>::point_update(int, T) [with T = int]'
examination.cpp:137:36:   required from here
examination.cpp:29:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int middle = l + r >> 1;
      |                ~~^~~
examination.cpp: In instantiation of 'T segment_tree<T>::query(int, int, int, int, int) [with T = int]':
examination.cpp:40:32:   required from 'T segment_tree<T>::query(int, int) [with T = int]'
examination.cpp:141:34:   required from here
examination.cpp:46:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int middle = l + r >> 1;
      |                ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28524 KB Output is correct
2 Correct 18 ms 28488 KB Output is correct
3 Correct 18 ms 28524 KB Output is correct
4 Correct 18 ms 28524 KB Output is correct
5 Correct 18 ms 28524 KB Output is correct
6 Correct 18 ms 28524 KB Output is correct
7 Correct 38 ms 29932 KB Output is correct
8 Correct 36 ms 29932 KB Output is correct
9 Correct 35 ms 29932 KB Output is correct
10 Correct 30 ms 29568 KB Output is correct
11 Correct 33 ms 29548 KB Output is correct
12 Correct 26 ms 28908 KB Output is correct
13 Correct 33 ms 29676 KB Output is correct
14 Correct 33 ms 29676 KB Output is correct
15 Correct 36 ms 29676 KB Output is correct
16 Correct 29 ms 29292 KB Output is correct
17 Correct 30 ms 29548 KB Output is correct
18 Correct 25 ms 28780 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 50472 KB Output is correct
2 Correct 714 ms 49920 KB Output is correct
3 Correct 713 ms 49968 KB Output is correct
4 Correct 391 ms 45012 KB Output is correct
5 Correct 452 ms 45084 KB Output is correct
6 Correct 279 ms 37916 KB Output is correct
7 Correct 689 ms 49052 KB Output is correct
8 Correct 667 ms 49052 KB Output is correct
9 Correct 630 ms 48156 KB Output is correct
10 Correct 400 ms 44920 KB Output is correct
11 Correct 378 ms 44956 KB Output is correct
12 Correct 255 ms 37148 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 50472 KB Output is correct
2 Correct 714 ms 49920 KB Output is correct
3 Correct 713 ms 49968 KB Output is correct
4 Correct 391 ms 45012 KB Output is correct
5 Correct 452 ms 45084 KB Output is correct
6 Correct 279 ms 37916 KB Output is correct
7 Correct 689 ms 49052 KB Output is correct
8 Correct 667 ms 49052 KB Output is correct
9 Correct 630 ms 48156 KB Output is correct
10 Correct 400 ms 44920 KB Output is correct
11 Correct 378 ms 44956 KB Output is correct
12 Correct 255 ms 37148 KB Output is correct
13 Correct 872 ms 53604 KB Output is correct
14 Correct 781 ms 52508 KB Output is correct
15 Correct 712 ms 49904 KB Output is correct
16 Correct 488 ms 47388 KB Output is correct
17 Correct 557 ms 47380 KB Output is correct
18 Correct 286 ms 37648 KB Output is correct
19 Correct 858 ms 53660 KB Output is correct
20 Correct 814 ms 52764 KB Output is correct
21 Correct 888 ms 53788 KB Output is correct
22 Correct 406 ms 44956 KB Output is correct
23 Correct 365 ms 44956 KB Output is correct
24 Correct 258 ms 37276 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28524 KB Output is correct
2 Correct 18 ms 28488 KB Output is correct
3 Correct 18 ms 28524 KB Output is correct
4 Correct 18 ms 28524 KB Output is correct
5 Correct 18 ms 28524 KB Output is correct
6 Correct 18 ms 28524 KB Output is correct
7 Correct 38 ms 29932 KB Output is correct
8 Correct 36 ms 29932 KB Output is correct
9 Correct 35 ms 29932 KB Output is correct
10 Correct 30 ms 29568 KB Output is correct
11 Correct 33 ms 29548 KB Output is correct
12 Correct 26 ms 28908 KB Output is correct
13 Correct 33 ms 29676 KB Output is correct
14 Correct 33 ms 29676 KB Output is correct
15 Correct 36 ms 29676 KB Output is correct
16 Correct 29 ms 29292 KB Output is correct
17 Correct 30 ms 29548 KB Output is correct
18 Correct 25 ms 28780 KB Output is correct
19 Correct 729 ms 50472 KB Output is correct
20 Correct 714 ms 49920 KB Output is correct
21 Correct 713 ms 49968 KB Output is correct
22 Correct 391 ms 45012 KB Output is correct
23 Correct 452 ms 45084 KB Output is correct
24 Correct 279 ms 37916 KB Output is correct
25 Correct 689 ms 49052 KB Output is correct
26 Correct 667 ms 49052 KB Output is correct
27 Correct 630 ms 48156 KB Output is correct
28 Correct 400 ms 44920 KB Output is correct
29 Correct 378 ms 44956 KB Output is correct
30 Correct 255 ms 37148 KB Output is correct
31 Correct 872 ms 53604 KB Output is correct
32 Correct 781 ms 52508 KB Output is correct
33 Correct 712 ms 49904 KB Output is correct
34 Correct 488 ms 47388 KB Output is correct
35 Correct 557 ms 47380 KB Output is correct
36 Correct 286 ms 37648 KB Output is correct
37 Correct 858 ms 53660 KB Output is correct
38 Correct 814 ms 52764 KB Output is correct
39 Correct 888 ms 53788 KB Output is correct
40 Correct 406 ms 44956 KB Output is correct
41 Correct 365 ms 44956 KB Output is correct
42 Correct 258 ms 37276 KB Output is correct
43 Correct 1104 ms 69096 KB Output is correct
44 Correct 1092 ms 69036 KB Output is correct
45 Correct 972 ms 67996 KB Output is correct
46 Correct 572 ms 59500 KB Output is correct
47 Correct 677 ms 59584 KB Output is correct
48 Correct 293 ms 37916 KB Output is correct
49 Correct 1018 ms 68892 KB Output is correct
50 Correct 1121 ms 69684 KB Output is correct
51 Correct 1090 ms 70428 KB Output is correct
52 Correct 568 ms 59548 KB Output is correct
53 Correct 397 ms 53148 KB Output is correct