oj.uz

Submission #497648

# Submission time Handle Problem Language Result Execution time Memory
497648 2021-12-23T12:58:49 Z penguin133 Examination (JOI19_examination) C++17
100 / 100
 711 ms 242156 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int n,q;
pair<int, pair<int, pair<int, int> > > Q[100005];
pair<int, pair<int, int> > X[100005];
int ans[100005];
struct node{
	int s,e,m,val,val2;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		l = r = nullptr;
	}
	void mc(){
		if(l != nullptr)return;
		if(s != e){
			l = new node(s,m);
			r = new node(m+1,e);
		}
	}
	void up1(int p, int v){
		if(s == e)val += v;
		else{
			mc();
			if(p <= m)l->up1(p,v);
			else r->up1(p,v);
			val = l->val + r->val;
		}
	}
	void up2(int p, int v){
		if(s == e)val2 += v;
		else{
			mc();
			if(p <= m)l->up2(p,v);
			else r->up2(p,v);
			val2 = l->val2 + r->val2;
		}
	}
	int q1(int a, int b){
		if(l == nullptr)return val;
		else if(s == a && b == e)return val;
		else if(b <= m)return l->q1(a,b);
		else if(a > m)return r->q1(a,b);
		else return l->q1(a,m) + r->q1(m+1, b);
	}
	int q2(int a,int b){
		if(l == nullptr)return val2;
		else if(s == a && b == e)return val2;
		else if(b <= m)return l->q2(a,b);
		else if(a > m)return r->q2(a,b);
		else return l->q2(a,m) + r->q2(m+1, b);
	}
}*root;
int main(){
	//ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> q;
	for(int i=1;i<=n;i++)cin >> X[i].s.f >> X[i].s.s, X[i].f = X[i].s.f + X[i].s.s;
	for(int i=1;i<=q;i++)cin >> Q[i].s.f >> Q[i].s.s.f >> Q[i].f, Q[i].f = max(Q[i]. f, Q[i].s.f + Q[i].s.s.f), Q[i].s.s.s = i;
	sort(Q+1, Q+q+1);
	sort(X+1, X+n+1);
	root = new node(0, 1e9 + 100);
	int in = n, ans2 = 0;
	for(int i=q;i>=1;i--){
		int w = Q[i].f, x = Q[i].s.f, y = Q[i].s.s.f, z = Q[i].s.s.s;
		//cout << w << " " << x << '\n';
		while(in >= 1 && X[in].f >= w){
			ans2++;
			root->up1(X[in].s.f, 1);
			root->up2(X[in].s.s, 1);
			in--;
		}
		ans[z]  =ans2;
		if(x > 0)ans[z] -= root->q1(0,x-1);
		if(y > 0)ans[z] -= root->q2(0,y-1);
	}
	for(int i=1;i<=q;i++)cout << ans[i] << '\n';
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 24 ms 10296 KB Output is correct
8 Correct 18 ms 10328 KB Output is correct
9 Correct 16 ms 10220 KB Output is correct
10 Correct 11 ms 5556 KB Output is correct
11 Correct 10 ms 5588 KB Output is correct
12 Correct 4 ms 356 KB Output is correct
13 Correct 17 ms 10348 KB Output is correct
14 Correct 21 ms 10312 KB Output is correct
15 Correct 17 ms 10308 KB Output is correct
16 Correct 14 ms 5584 KB Output is correct
17 Correct 11 ms 5564 KB Output is correct
18 Correct 4 ms 444 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 15716 KB Output is correct
2 Correct 278 ms 15712 KB Output is correct
3 Correct 275 ms 15660 KB Output is correct
4 Correct 167 ms 14436 KB Output is correct
5 Correct 180 ms 14432 KB Output is correct
6 Correct 139 ms 4932 KB Output is correct
7 Correct 255 ms 15628 KB Output is correct
8 Correct 244 ms 15612 KB Output is correct
9 Correct 260 ms 15532 KB Output is correct
10 Correct 171 ms 14184 KB Output is correct
11 Correct 164 ms 14284 KB Output is correct
12 Correct 118 ms 4624 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 15716 KB Output is correct
2 Correct 278 ms 15712 KB Output is correct
3 Correct 275 ms 15660 KB Output is correct
4 Correct 167 ms 14436 KB Output is correct
5 Correct 180 ms 14432 KB Output is correct
6 Correct 139 ms 4932 KB Output is correct
7 Correct 255 ms 15628 KB Output is correct
8 Correct 244 ms 15612 KB Output is correct
9 Correct 260 ms 15532 KB Output is correct
10 Correct 171 ms 14184 KB Output is correct
11 Correct 164 ms 14284 KB Output is correct
12 Correct 118 ms 4624 KB Output is correct
13 Correct 295 ms 16108 KB Output is correct
14 Correct 288 ms 16036 KB Output is correct
15 Correct 273 ms 15716 KB Output is correct
16 Correct 182 ms 14820 KB Output is correct
17 Correct 192 ms 14764 KB Output is correct
18 Correct 136 ms 4984 KB Output is correct
19 Correct 290 ms 16112 KB Output is correct
20 Correct 318 ms 16236 KB Output is correct
21 Correct 287 ms 16124 KB Output is correct
22 Correct 182 ms 14228 KB Output is correct
23 Correct 182 ms 14180 KB Output is correct
24 Correct 132 ms 4568 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 24 ms 10296 KB Output is correct
8 Correct 18 ms 10328 KB Output is correct
9 Correct 16 ms 10220 KB Output is correct
10 Correct 11 ms 5556 KB Output is correct
11 Correct 10 ms 5588 KB Output is correct
12 Correct 4 ms 356 KB Output is correct
13 Correct 17 ms 10348 KB Output is correct
14 Correct 21 ms 10312 KB Output is correct
15 Correct 17 ms 10308 KB Output is correct
16 Correct 14 ms 5584 KB Output is correct
17 Correct 11 ms 5564 KB Output is correct
18 Correct 4 ms 444 KB Output is correct
19 Correct 260 ms 15716 KB Output is correct
20 Correct 278 ms 15712 KB Output is correct
21 Correct 275 ms 15660 KB Output is correct
22 Correct 167 ms 14436 KB Output is correct
23 Correct 180 ms 14432 KB Output is correct
24 Correct 139 ms 4932 KB Output is correct
25 Correct 255 ms 15628 KB Output is correct
26 Correct 244 ms 15612 KB Output is correct
27 Correct 260 ms 15532 KB Output is correct
28 Correct 171 ms 14184 KB Output is correct
29 Correct 164 ms 14284 KB Output is correct
30 Correct 118 ms 4624 KB Output is correct
31 Correct 295 ms 16108 KB Output is correct
32 Correct 288 ms 16036 KB Output is correct
33 Correct 273 ms 15716 KB Output is correct
34 Correct 182 ms 14820 KB Output is correct
35 Correct 192 ms 14764 KB Output is correct
36 Correct 136 ms 4984 KB Output is correct
37 Correct 290 ms 16112 KB Output is correct
38 Correct 318 ms 16236 KB Output is correct
39 Correct 287 ms 16124 KB Output is correct
40 Correct 182 ms 14228 KB Output is correct
41 Correct 182 ms 14180 KB Output is correct
42 Correct 132 ms 4568 KB Output is correct
43 Correct 711 ms 242144 KB Output is correct
44 Correct 696 ms 242096 KB Output is correct
45 Correct 699 ms 242156 KB Output is correct
46 Correct 340 ms 133112 KB Output is correct
47 Correct 335 ms 132732 KB Output is correct
48 Correct 181 ms 4760 KB Output is correct
49 Correct 706 ms 242152 KB Output is correct
50 Correct 688 ms 242140 KB Output is correct
51 Correct 639 ms 241884 KB Output is correct
52 Correct 333 ms 132904 KB Output is correct
53 Correct 296 ms 132364 KB Output is correct