oj.uz

Submission #383970

# Submission time Handle Problem Language Result Execution time Memory
383970 2021-03-31T06:00:50 Z nikatamliani Examination (JOI19_examination) C++14
100 / 100
 781 ms 76116 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+10;
template <typename T>
struct implicit_segment_tree {
	T neutral;
	int size, max_size;
	function<T(T, T)> join;
	vector<T> values;
	vector<int> left, right;
	implicit_segment_tree(int _max_size, T _neutral, function<T(T, T)> f, int reserve_size = 1) {
		join = f;
		neutral = _neutral;
		size = 0;
		max_size = _max_size;
		values.reserve(reserve_size);
		left.reserve(reserve_size);
		right.reserve(reserve_size);
		insert_node(neutral);
	}
	
	T get_val(int pos) {
		if(pos < 0 || pos >= (int)values.size()) return neutral;
		return values[pos];
	}
	
	void insert_node(T val) {
		values.push_back(val);
		left.push_back(-1);
		right.push_back(-1);
		++size;
	}
	
	void point_update(int id, T val) {
		point_update(-max_size, max_size, id, val, 0); 
	}
	
	void point_update(int l, int r, int x, T val, int p) {
		int middle = l + r >> 1;
		if(l == r) {
			values[p] = val;
			return;
		}
		if(x <= middle) {
			if(left[p] == -1) {
				left[p] = size;
				insert_node(neutral);
			}
			point_update(l, middle, x, val, left[p]);
		} else {
			if(right[p] == -1) {
				right[p] = size;
				insert_node(neutral);
			}
			point_update(middle+1, r, x, val, right[p]);
		}
		values[p] = join(get_val(left[p]), get_val(right[p]));
	}
	
	T get(int id) {
		return query(id, id);
	}
	
	T query(int L, int R) {
		if(L > R) return neutral;
		return query(-max_size, max_size, L, R, 0); 
	}
	
	T query(int l, int r, int L, int R, int p) {
		if(L > r || l > R || p == -1) return neutral;
		if(L <= l && R >= r) return get_val(p);
		int middle = l + r >> 1;
		T lft = query(l, middle, L, R, left[p]);
		T rgh = query(middle+1, r, L, R, right[p]);
		return join(lft, rgh);
	}
	
	void print_tree(int n) {
		for(int i = 1; i <= n; ++i) {
			cout << get(i) << " \n"[i == n];
		}
	}
};
struct point {
	int x, y, sum, id;
	bool operator < (const point &other) {
		return sum < other.sum;
	}
};
main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m; 
	vector<point> a(n), b(m);
	for(int i = 0; i < n; ++i) {
		cin >> a[i].x >> a[i].y;
		a[i].sum = a[i].x + a[i].y;
	}
	for(int i = 0; i < m; ++i) {
		cin >> b[i].x >> b[i].y >> b[i].sum;
		b[i].sum = max(b[i].sum, b[i].x + b[i].y);
		b[i].id = i;
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	vector<int> ans(m);
	auto sum = [](int x, int y) -> int {
		return x + y;
	};
	implicit_segment_tree<int> tx(INT_MAX, 0, sum);
	implicit_segment_tree<int> ty(INT_MAX, 0, sum); 
	for(int i = m - 1, j = n - 1; i >= 0; --i) {
		while(j >= 0 && a[j].sum >= b[i].sum) {
			int upd_x = tx.get(a[j].x) + 1;
			int upd_y = ty.get(a[j].y) + 1;
			tx.point_update(a[j].x, upd_x);
			ty.point_update(a[j].y, upd_y);
			--j;
		}
		ans[b[i].id] = n - j - 1 - tx.query(0, b[i].x - 1) - ty.query(0, b[i].y - 1);
	}
	for(int x : ans) {
		cout << x << ' ';  
	}
}

Compilation message

examination.cpp:91:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main() {
      |      ^
examination.cpp: In instantiation of 'void implicit_segment_tree<T>::point_update(long long int, long long int, long long int, T, long long int) [with T = long long int]':
examination.cpp:36:3:   required from 'void implicit_segment_tree<T>::point_update(long long int, T) [with T = long long int]'
examination.cpp:117:33:   required from here
examination.cpp:40:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int middle = l + r >> 1;
      |                ~~^~~
examination.cpp: In instantiation of 'T implicit_segment_tree<T>::query(long long int, long long int, long long int, long long int, long long int) [with T = long long int]':
examination.cpp:67:44:   required from 'T implicit_segment_tree<T>::query(long long int, long long int) [with T = long long int]'
examination.cpp:121:52:   required from here
examination.cpp:73:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |   int middle = l + r >> 1;
      |                ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 14 ms 3732 KB Output is correct
8 Correct 14 ms 3708 KB Output is correct
9 Correct 14 ms 3404 KB Output is correct
10 Correct 13 ms 2264 KB Output is correct
11 Correct 12 ms 2312 KB Output is correct
12 Correct 13 ms 620 KB Output is correct
13 Correct 15 ms 3752 KB Output is correct
14 Correct 15 ms 3732 KB Output is correct
15 Correct 14 ms 3420 KB Output is correct
16 Correct 11 ms 2136 KB Output is correct
17 Correct 11 ms 2156 KB Output is correct
18 Correct 7 ms 620 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 15540 KB Output is correct
2 Correct 512 ms 15644 KB Output is correct
3 Correct 572 ms 15684 KB Output is correct
4 Correct 371 ms 11848 KB Output is correct
5 Correct 378 ms 11872 KB Output is correct
6 Correct 312 ms 8044 KB Output is correct
7 Correct 520 ms 15728 KB Output is correct
8 Correct 571 ms 15544 KB Output is correct
9 Correct 534 ms 15756 KB Output is correct
10 Correct 343 ms 11728 KB Output is correct
11 Correct 327 ms 11728 KB Output is correct
12 Correct 230 ms 7660 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 15540 KB Output is correct
2 Correct 512 ms 15644 KB Output is correct
3 Correct 572 ms 15684 KB Output is correct
4 Correct 371 ms 11848 KB Output is correct
5 Correct 378 ms 11872 KB Output is correct
6 Correct 312 ms 8044 KB Output is correct
7 Correct 520 ms 15728 KB Output is correct
8 Correct 571 ms 15544 KB Output is correct
9 Correct 534 ms 15756 KB Output is correct
10 Correct 343 ms 11728 KB Output is correct
11 Correct 327 ms 11728 KB Output is correct
12 Correct 230 ms 7660 KB Output is correct
13 Correct 507 ms 15644 KB Output is correct
14 Correct 528 ms 15464 KB Output is correct
15 Correct 511 ms 15648 KB Output is correct
16 Correct 361 ms 11840 KB Output is correct
17 Correct 373 ms 11720 KB Output is correct
18 Correct 305 ms 8044 KB Output is correct
19 Correct 541 ms 15624 KB Output is correct
20 Correct 552 ms 15684 KB Output is correct
21 Correct 517 ms 15964 KB Output is correct
22 Correct 317 ms 11740 KB Output is correct
23 Correct 322 ms 11600 KB Output is correct
24 Correct 206 ms 7660 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 14 ms 3732 KB Output is correct
8 Correct 14 ms 3708 KB Output is correct
9 Correct 14 ms 3404 KB Output is correct
10 Correct 13 ms 2264 KB Output is correct
11 Correct 12 ms 2312 KB Output is correct
12 Correct 13 ms 620 KB Output is correct
13 Correct 15 ms 3752 KB Output is correct
14 Correct 15 ms 3732 KB Output is correct
15 Correct 14 ms 3420 KB Output is correct
16 Correct 11 ms 2136 KB Output is correct
17 Correct 11 ms 2156 KB Output is correct
18 Correct 7 ms 620 KB Output is correct
19 Correct 549 ms 15540 KB Output is correct
20 Correct 512 ms 15644 KB Output is correct
21 Correct 572 ms 15684 KB Output is correct
22 Correct 371 ms 11848 KB Output is correct
23 Correct 378 ms 11872 KB Output is correct
24 Correct 312 ms 8044 KB Output is correct
25 Correct 520 ms 15728 KB Output is correct
26 Correct 571 ms 15544 KB Output is correct
27 Correct 534 ms 15756 KB Output is correct
28 Correct 343 ms 11728 KB Output is correct
29 Correct 327 ms 11728 KB Output is correct
30 Correct 230 ms 7660 KB Output is correct
31 Correct 507 ms 15644 KB Output is correct
32 Correct 528 ms 15464 KB Output is correct
33 Correct 511 ms 15648 KB Output is correct
34 Correct 361 ms 11840 KB Output is correct
35 Correct 373 ms 11720 KB Output is correct
36 Correct 305 ms 8044 KB Output is correct
37 Correct 541 ms 15624 KB Output is correct
38 Correct 552 ms 15684 KB Output is correct
39 Correct 517 ms 15964 KB Output is correct
40 Correct 317 ms 11740 KB Output is correct
41 Correct 322 ms 11600 KB Output is correct
42 Correct 206 ms 7660 KB Output is correct
43 Correct 708 ms 76116 KB Output is correct
44 Correct 683 ms 76052 KB Output is correct
45 Correct 781 ms 75900 KB Output is correct
46 Correct 397 ms 42112 KB Output is correct
47 Correct 401 ms 41820 KB Output is correct
48 Correct 241 ms 7916 KB Output is correct
49 Correct 754 ms 76048 KB Output is correct
50 Correct 687 ms 76096 KB Output is correct
51 Correct 731 ms 76036 KB Output is correct
52 Correct 352 ms 41864 KB Output is correct
53 Correct 360 ms 42016 KB Output is correct