oj.uz

Submission #124351

# Submission time Handle Problem Language Result Execution time Memory
124351 2019-07-03T07:11:55 Z Adhyyan1252 Tenis (COI19_tenis) C++11
100 / 100
 482 ms 13380 KB 
#include<bits/stdc++.h>

using namespace std;

//let ai hold the size of union of prefix
//find minimum ai - i
//update the prefix 

#define INF 1e7
struct segtree{
	vector<int> t,l;
	int sz;
	
	segtree(int size){
		sz = size;
		t = vector<int>(sz*4, 0);
		l = vector<int>(sz*4, 0);
	}
	
	void prop(int i, int s, int e){
		if(l[i] == 0) return;
		t[i] += l[i];
		if(s != e){
			l[i*2] += l[i];
			l[i*2+1] += l[i];
		}
		l[i] = 0;
	}
	
	int query(int i, int s, int e, int l, int r){
		prop(i, s, e);
		if(s > r || e < l || s > e) return INF;
		if(l <= s && e <= r) return t[i];
		int m = (s + e)/2;
		return min(query(i*2, s, m, l, r), query(i*2+1, m+1, e, l, r));
	}
	
	void upd(int i, int s, int e, int L, int r, int val){
		prop(i, s, e);
		if(L <= s && e <= r){
			l[i] = val;
			prop(i, s, e);
			return;
		}
		if(s > r || e < L) return;
		int m = (s + e)/2;
		upd(i*2, s, m, L, r, val);
		upd(i*2+1, m+1, e, L, r, val);
		t[i] = min(t[i*2], t[i*2+1]);
	}
	
	
};


int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int n, q; cin>>n>>q;
	vector<vector<int> > perm(3, vector<int>(n));
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < n; j++){
			cin>>perm[i][j];
			perm[i][j]--;
		}
	}
	
	vector<vector<int> > a(n, vector<int>(3));
	for(int j = 0; j < 3; j++){
		for(int i = 0; i < n; i++){
			a[perm[j][i]][j] = i;
		}
	}
	
	segtree s(n);
	
	for(int i = 0; i < n; i++){
		s.upd(1, 0, s.sz-1, i, i, -(i+1));
	}
	for(int i = 0; i < n; i++){
		int low = INF;
		for(int j = 0; j < 3; j++) low = min(low, a[i][j]);
		s.upd(1, 0, s.sz-1, low, s.sz-1, 1);
	}
	
	for(int qt = 0; qt < q; qt++){
		int type; cin>>type; 
		if(type == 1){
			int indx; cin>>indx; indx--;
			int low = INF;
			for(int j = 0; j < 3; j++) low = min(low, a[indx][j]);
			int ret = s.query(1, 0, s.sz-1, 0, low-1);
			//cout<<"Q "<<indx<<" "<<low<<" "<<ret<<endl;
			assert(ret >= 0);
			if(ret == 0){
				cout<<"NE"<<endl;
			}else{
				cout<<"DA"<<endl;
			}
		}else{
			int p, x, y; cin>>p>>x>>y; p--, x--, y--;
			
			//first remove from segtree
			
			{
				int low = INF;
				for(int j = 0; j < 3; j++) low = min(low, a[x][j]);
				s.upd(1, 0, s.sz-1, low, s.sz-1, -1);
			}
			{
				int low = INF;
				for(int j = 0; j < 3; j++) low = min(low, a[y][j]);
				s.upd(1, 0, s.sz-1, low, s.sz-1, -1);
			}
			
			swap(a[x][p], a[y][p]);
			
			{
				int low = INF;
				for(int j = 0; j < 3; j++) low = min(low, a[x][j]);
				s.upd(1, 0, s.sz-1, low, s.sz-1, 1);
			}
			{
				int low = INF;
				for(int j = 0; j < 3; j++) low = min(low, a[y][j]);
				s.upd(1, 0, s.sz-1, low, s.sz-1, 1);
			}	
		}
	}
	
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 115 ms 11884 KB Output is correct
14 Correct 116 ms 11756 KB Output is correct
15 Correct 115 ms 11760 KB Output is correct
16 Correct 115 ms 11888 KB Output is correct
17 Correct 117 ms 11824 KB Output is correct
18 Correct 117 ms 11888 KB Output is correct
19 Correct 116 ms 11892 KB Output is correct
20 Correct 115 ms 11860 KB Output is correct
21 Correct 117 ms 11884 KB Output is correct
22 Correct 118 ms 12032 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 13048 KB Output is correct
2 Correct 464 ms 13040 KB Output is correct
3 Correct 458 ms 13056 KB Output is correct
4 Correct 482 ms 13032 KB Output is correct
5 Correct 460 ms 12916 KB Output is correct
6 Correct 459 ms 12904 KB Output is correct
7 Correct 476 ms 13032 KB Output is correct
8 Correct 462 ms 13140 KB Output is correct
9 Correct 461 ms 13164 KB Output is correct
10 Correct 470 ms 13028 KB Output is correct
11 Correct 463 ms 12912 KB Output is correct
12 Correct 461 ms 12940 KB Output is correct
13 Correct 459 ms 12948 KB Output is correct
14 Correct 463 ms 12952 KB Output is correct
15 Correct 458 ms 12968 KB Output is correct

Subtask #5
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 115 ms 11884 KB Output is correct
14 Correct 116 ms 11756 KB Output is correct
15 Correct 115 ms 11760 KB Output is correct
16 Correct 115 ms 11888 KB Output is correct
17 Correct 117 ms 11824 KB Output is correct
18 Correct 117 ms 11888 KB Output is correct
19 Correct 116 ms 11892 KB Output is correct
20 Correct 115 ms 11860 KB Output is correct
21 Correct 117 ms 11884 KB Output is correct
22 Correct 118 ms 12032 KB Output is correct
23 Correct 461 ms 13048 KB Output is correct
24 Correct 464 ms 13040 KB Output is correct
25 Correct 458 ms 13056 KB Output is correct
26 Correct 482 ms 13032 KB Output is correct
27 Correct 460 ms 12916 KB Output is correct
28 Correct 459 ms 12904 KB Output is correct
29 Correct 476 ms 13032 KB Output is correct
30 Correct 462 ms 13140 KB Output is correct
31 Correct 461 ms 13164 KB Output is correct
32 Correct 470 ms 13028 KB Output is correct
33 Correct 463 ms 12912 KB Output is correct
34 Correct 461 ms 12940 KB Output is correct
35 Correct 459 ms 12948 KB Output is correct
36 Correct 463 ms 12952 KB Output is correct
37 Correct 458 ms 12968 KB Output is correct
38 Correct 352 ms 13172 KB Output is correct
39 Correct 440 ms 12964 KB Output is correct
40 Correct 357 ms 13312 KB Output is correct
41 Correct 396 ms 13012 KB Output is correct
42 Correct 384 ms 13272 KB Output is correct
43 Correct 377 ms 13352 KB Output is correct
44 Correct 428 ms 13084 KB Output is correct
45 Correct 386 ms 13172 KB Output is correct
46 Correct 415 ms 13012 KB Output is correct
47 Correct 416 ms 13044 KB Output is correct
48 Correct 415 ms 12916 KB Output is correct
49 Correct 381 ms 13168 KB Output is correct
50 Correct 417 ms 13040 KB Output is correct
51 Correct 383 ms 13040 KB Output is correct
52 Correct 347 ms 13264 KB Output is correct
53 Correct 389 ms 13380 KB Output is correct
54 Correct 377 ms 13016 KB Output is correct
55 Correct 427 ms 13160 KB Output is correct
56 Correct 380 ms 13060 KB Output is correct
57 Correct 414 ms 13296 KB Output is correct
58 Correct 423 ms 13168 KB Output is correct