oj.uz

Submission #230023

# Submission time Handle Problem Language Result Execution time Memory
230023 2020-05-07T19:32:48 Z AQT Game (IOI13_game) C++14
100 / 100
 8714 ms 67936 KB 
#include <game.h>
#include <bits/stdc++.h>

using namespace std;

mt19937 rando (chrono::steady_clock::now().time_since_epoch().count());

struct snode {
	pair<int, int> p;
	long long x, g;
	int pri;
	snode * c[2];
	snode (int pp1, int pp2, long long v){
		p = {pp1, pp2};
		x = g = v;
		pri = uniform_int_distribution<int>(INT_MIN, INT_MAX) (rando);
		c[0] = c[1] = NULL;
	}
};

struct bnode {
	snode * rt;
	bnode * lft, * rht;
	bnode(){
		lft = rht = NULL;
		rt = NULL;
	}
};

bnode * rt;
int N;

long long getg(snode * n){
	return n ? n->g : 0;
}

snode * pu(snode * n){
	n->g = __gcd(__gcd(getg(n->c[0]), getg(n->c[1])), n->x);
	return n;
}

pair<snode *, snode *> split(snode * n, pair<int, int> k){
	if(!n){
		return {n, n};
	}
	if(n->p >= k){
		auto p = split(n->c[0], k);
		n->c[0] = p.second;
		return {p.first, pu(n)};
	}
	else{
		auto p = split(n->c[1], k);
		n->c[1] = p.first;
		return {pu(n), p.second};
	}
}

pair<snode *, snode*> split(snode * n, int x, int y){
	return split(n, {x, y});
}

snode * merge(snode * lft, snode * rht){
	if(!lft){
		return rht;
	}
	if(!rht){
		return lft;
	}
	if(lft->pri > rht->pri){
		lft->c[1] = merge(lft->c[1], rht);
		return pu(lft);
	}
	else{
		rht->c[0] = merge(lft, rht->c[0]);
		return pu(rht);
	}
}

bnode * upd(int l, int r, int x, int y, long long v, bnode * n){
	//cout << l << " " << r << "\n";
	if(n == NULL){
		n = new bnode();
	}
	auto p = split(n->rt, y, x);
	auto q = split(p.second, y, x+1);
	n->rt = merge(p.first, merge(new snode(y, x, v), q.second));
	if(l == r){
		return n;
	}
	int mid = l+r>>1;
	if(x <= mid){
		n->lft = upd(l, mid, x, y, v, n->lft);
	}
	else{
		n->rht = upd(mid+1, r, x, y, v, n->rht);
	}
	return n;
}

long long query(int sl, int sr, int ql, int qr, int qsl, int qsr, bnode * n){
	if(n == NULL || sr < ql || sl > qr){
		return 0;
	}
	//cout << " " << sl << " " << sr << "\n";
	if(ql <= sl && qr >= sr){
		//cout << " " << n->rt->g << "\n";
		auto p = split(n->rt, qsl, -1);
		auto q = split(p.second, qsr+1, -1);
		long long ret = getg(q.first);
		n->rt = merge(p.first, merge(q.first, q.second));
		return ret;
	}
	int mid = sl+sr>>1;
	return __gcd(query(sl, mid, ql, qr, qsl, qsr, n->lft), query(mid+1, sr, ql, qr, qsl, qsr, n->rht));
}

void init(int R, int C){
	N = R-1;
}

void update(int r, int c, long long v){
	rt = upd(0, N, r, c, v, rt);
}

long long calculate(int r, int c, int sr, int sc){
	return query(0, N, r, sr, c, sc, rt);
}

/*
int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	init(2, 3);
	update(0, 0, 20);
	update(0, 2, 15);
	update(1, 1, 12);
	cout << calculate(0, 0, 0, 2) << "\n";
	cout << calculate(0, 0, 1, 1) << "\n";
	update(0, 1, 6);
	update(1, 1, 14);
	cout << calculate(0, 0, 0, 2) << "\n";
	cout << calculate(0, 0, 1, 1) << "\n";
}
*/

/*
int main(){
	init(1000000000, 1000000000);
	update(0, 0, 1000000000000000000);
	update(999999999, 999999999, 1);
	cout << calculate(0, 0, 999999999, 999999999) << "\n";
}
*/
/*
int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int A, B, Q;
	cin >> A >> B >> Q;
	init(A, B);
	while(Q--){
		int k;
		cin >> k;
		if(k == 1){
			int r, c;
			long long v;
			cin >> r >> c >> v;
			update(r, c, v);
		}
		else{
			int r1, c1, r2, c2;
			cin >> r1 >> c1 >> r2 >> c2;
			cout << calculate(r1, c1, r2, c2) << "\n";
		}
	}
}
*/

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
game.cpp: In function 'bnode* upd(int, int, int, int, long long int, bnode*)':
game.cpp:90:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r>>1;
            ~^~
game.cpp: In function 'long long int query(int, int, int, int, int, int, bnode*)':
game.cpp:113:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = sl+sr>>1;
            ~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 1031 ms 11556 KB Output is correct
5 Correct 450 ms 11512 KB Output is correct
6 Correct 1261 ms 9072 KB Output is correct
7 Correct 1445 ms 8696 KB Output is correct
8 Correct 981 ms 7608 KB Output is correct
9 Correct 1383 ms 8760 KB Output is correct
10 Correct 1234 ms 8404 KB Output is correct
11 Correct 4 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 432 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 1533 ms 15736 KB Output is correct
13 Correct 4318 ms 12200 KB Output is correct
14 Correct 696 ms 13176 KB Output is correct
15 Correct 4386 ms 13220 KB Output is correct
16 Correct 535 ms 13048 KB Output is correct
17 Correct 1922 ms 10492 KB Output is correct
18 Correct 3508 ms 14568 KB Output is correct
19 Correct 2904 ms 14596 KB Output is correct
20 Correct 2727 ms 14060 KB Output is correct
21 Correct 5 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 1002 ms 11716 KB Output is correct
13 Correct 437 ms 11384 KB Output is correct
14 Correct 1243 ms 8824 KB Output is correct
15 Correct 1436 ms 8760 KB Output is correct
16 Correct 964 ms 7672 KB Output is correct
17 Correct 1370 ms 8952 KB Output is correct
18 Correct 1227 ms 8464 KB Output is correct
19 Correct 1532 ms 15580 KB Output is correct
20 Correct 4211 ms 11896 KB Output is correct
21 Correct 713 ms 13048 KB Output is correct
22 Correct 4454 ms 13224 KB Output is correct
23 Correct 440 ms 13048 KB Output is correct
24 Correct 1939 ms 10232 KB Output is correct
25 Correct 3692 ms 14512 KB Output is correct
26 Correct 2869 ms 14504 KB Output is correct
27 Correct 2656 ms 13920 KB Output is correct
28 Correct 1156 ms 36312 KB Output is correct
29 Correct 2216 ms 39160 KB Output is correct
30 Correct 5876 ms 30592 KB Output is correct
31 Correct 5159 ms 29900 KB Output is correct
32 Correct 1000 ms 29560 KB Output is correct
33 Correct 1405 ms 29700 KB Output is correct
34 Correct 588 ms 32888 KB Output is correct
35 Correct 2221 ms 24108 KB Output is correct
36 Correct 4158 ms 37208 KB Output is correct
37 Correct 3324 ms 37240 KB Output is correct
38 Correct 3236 ms 36560 KB Output is correct
39 Correct 2800 ms 31360 KB Output is correct
40 Correct 5 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 1018 ms 11600 KB Output is correct
13 Correct 421 ms 11512 KB Output is correct
14 Correct 1257 ms 8952 KB Output is correct
15 Correct 1467 ms 8656 KB Output is correct
16 Correct 970 ms 7608 KB Output is correct
17 Correct 1367 ms 8824 KB Output is correct
18 Correct 1266 ms 8312 KB Output is correct
19 Correct 1561 ms 15608 KB Output is correct
20 Correct 4202 ms 12368 KB Output is correct
21 Correct 710 ms 13048 KB Output is correct
22 Correct 4456 ms 13240 KB Output is correct
23 Correct 471 ms 13048 KB Output is correct
24 Correct 1909 ms 10488 KB Output is correct
25 Correct 3493 ms 14364 KB Output is correct
26 Correct 2861 ms 14616 KB Output is correct
27 Correct 2670 ms 14188 KB Output is correct
28 Correct 1173 ms 36764 KB Output is correct
29 Correct 2196 ms 39080 KB Output is correct
30 Correct 5865 ms 30520 KB Output is correct
31 Correct 4997 ms 30012 KB Output is correct
32 Correct 985 ms 29432 KB Output is correct
33 Correct 1364 ms 29560 KB Output is correct
34 Correct 538 ms 32888 KB Output is correct
35 Correct 2207 ms 23884 KB Output is correct
36 Correct 4224 ms 37044 KB Output is correct
37 Correct 3353 ms 37164 KB Output is correct
38 Correct 3285 ms 36656 KB Output is correct
39 Correct 1532 ms 65656 KB Output is correct
40 Correct 3641 ms 67936 KB Output is correct
41 Correct 8714 ms 57356 KB Output is correct
42 Correct 7678 ms 55848 KB Output is correct
43 Correct 913 ms 62456 KB Output is correct
44 Correct 1607 ms 53244 KB Output is correct
45 Correct 2842 ms 31096 KB Output is correct
46 Correct 5392 ms 66468 KB Output is correct
47 Correct 5459 ms 66548 KB Output is correct
48 Correct 5130 ms 66192 KB Output is correct
49 Correct 5 ms 256 KB Output is correct