oj.uz

Submission #471280

# Submission time Handle Problem Language Result Execution time Memory
471280 2021-09-08T06:26:36 Z CSQ31 Game (IOI13_game) C++17
100 / 100
 3780 ms 81992 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int r,c;
ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct node{
	node *L = NULL,*R = NULL;
	int l,r;
	ll val = 0;
	node(){}
	node(int _l,int _r):l(_l),r(_r){}
	void upd(int x,ll v){
		if(l == r){val = v;return;}
		int mid = (l+r)/2;
		node *& tp = (x<=mid?L : R);
		if(tp == NULL){
			tp = new node(x,x);
			tp->val = v;
		}else if(tp->l<=x && x<=tp->r)tp->upd(x,v);
		else{
			//we want to find the ancestor of this node and x
			int low = l;
			int high = r;
			while((x<=mid) == (tp->l <= mid)){
				if(x<=mid)high = mid;
				else low = mid+1;
				mid = (high+low)/2;
			}
			node * nn = new node(low,high);
			//we want to replace tp with nn then attach back the original shit as nn's child
			(tp->l<=mid?nn->L : nn->R) = tp;
			tp = nn;
			nn->upd(x,v);
		}
		val = gcd2(L==NULL?0:L->val,R == NULL?0:R->val);
	}
	ll query(int tl,int tr){
		if(tl<=l && r<=tr)return val;
		if(l > tr || tl > r)return 0;
		return gcd2(L?L->query(tl,tr):0 , R?R->query(tl,tr):0);
		
	}
};
struct nodex{
	nodex *L = NULL,*R = NULL;
	node tree;
	ll val = 0;
	nodex(){tree = node(1,c);}
}*root;
void upd(nodex *v,int x,int y,int l,int r,ll val){
	if(l==r){ 
		v->tree.upd(y,val);
		return;
	}
	else{
		int tm =(l+r)/2;
		if(x<=tm){
			if(v->L == NULL)v->L = new nodex();
			upd(v->L,x,y,l,tm,val);
		}else{
		    if(v->R == NULL)v->R = new nodex();
			upd(v->R,x,y,tm+1,r,val);
		}
	}
	ll k = gcd2(v->L == NULL?0:v->L->tree.query(y,y) , 
	            v->R == NULL?0:v->R->tree.query(y,y));
	            
	v->tree.upd(y,k);
	
}
ll query(nodex *v,int xl,int xr,int yl,int yr,int l,int r){
	if(xl == l && xr == r){
		return v->tree.query(yl,yr);
	}
	ll res = 0;
	int tm = (l+r)/2;
	if(xl<=tm && v->L != NULL)res = gcd2(query(v->L,xl,min(tm,xr),yl,yr,l,tm),res);	
	if(xr> tm && v->R != NULL)res = gcd2(query(v->R,max(xl,tm+1),xr,yl,yr,tm+1,r),res);
	return res;
}
void init(int R, int C) {
    r=R+1;
    c=C+1;
    root = new nodex();
}

void update(int P, int Q, ll K) {
	P++;
	Q++;
	upd(root,P,Q,1,r,K);
}

long long calculate(int P, int Q, int U, int V) {
	P++;
	Q++;
	U++;
	V++;
    return query(root,P,U,Q,V,1,r);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 502 ms 13148 KB Output is correct
5 Correct 355 ms 12740 KB Output is correct
6 Correct 489 ms 10180 KB Output is correct
7 Correct 548 ms 9944 KB Output is correct
8 Correct 363 ms 8076 KB Output is correct
9 Correct 556 ms 10052 KB Output is correct
10 Correct 473 ms 9888 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 874 ms 15704 KB Output is correct
13 Correct 1638 ms 8816 KB Output is correct
14 Correct 259 ms 5572 KB Output is correct
15 Correct 1829 ms 10516 KB Output is correct
16 Correct 644 ms 14036 KB Output is correct
17 Correct 725 ms 11028 KB Output is correct
18 Correct 1312 ms 15428 KB Output is correct
19 Correct 1146 ms 15648 KB Output is correct
20 Correct 991 ms 15024 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 501 ms 12868 KB Output is correct
13 Correct 351 ms 12724 KB Output is correct
14 Correct 488 ms 10256 KB Output is correct
15 Correct 538 ms 9920 KB Output is correct
16 Correct 358 ms 8188 KB Output is correct
17 Correct 514 ms 9936 KB Output is correct
18 Correct 520 ms 9676 KB Output is correct
19 Correct 883 ms 15696 KB Output is correct
20 Correct 1644 ms 8856 KB Output is correct
21 Correct 264 ms 5580 KB Output is correct
22 Correct 1831 ms 10536 KB Output is correct
23 Correct 637 ms 14084 KB Output is correct
24 Correct 720 ms 11080 KB Output is correct
25 Correct 1291 ms 15476 KB Output is correct
26 Correct 1110 ms 15656 KB Output is correct
27 Correct 1050 ms 15076 KB Output is correct
28 Correct 492 ms 43176 KB Output is correct
29 Correct 1290 ms 45324 KB Output is correct
30 Correct 2577 ms 35404 KB Output is correct
31 Correct 2354 ms 28676 KB Output is correct
32 Correct 386 ms 10332 KB Output is correct
33 Correct 510 ms 10740 KB Output is correct
34 Correct 799 ms 39100 KB Output is correct
35 Correct 1028 ms 26948 KB Output is correct
36 Correct 1978 ms 43268 KB Output is correct
37 Correct 1527 ms 43460 KB Output is correct
38 Correct 1528 ms 42880 KB Output is correct
39 Correct 1271 ms 35616 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 501 ms 12896 KB Output is correct
13 Correct 367 ms 12728 KB Output is correct
14 Correct 490 ms 10180 KB Output is correct
15 Correct 545 ms 9976 KB Output is correct
16 Correct 373 ms 8132 KB Output is correct
17 Correct 556 ms 10024 KB Output is correct
18 Correct 502 ms 9672 KB Output is correct
19 Correct 868 ms 15512 KB Output is correct
20 Correct 1634 ms 8744 KB Output is correct
21 Correct 265 ms 5556 KB Output is correct
22 Correct 1856 ms 10516 KB Output is correct
23 Correct 632 ms 14020 KB Output is correct
24 Correct 736 ms 10984 KB Output is correct
25 Correct 1476 ms 15552 KB Output is correct
26 Correct 1182 ms 15560 KB Output is correct
27 Correct 1113 ms 15228 KB Output is correct
28 Correct 479 ms 43168 KB Output is correct
29 Correct 1489 ms 45380 KB Output is correct
30 Correct 2603 ms 35120 KB Output is correct
31 Correct 2401 ms 28444 KB Output is correct
32 Correct 438 ms 10180 KB Output is correct
33 Correct 516 ms 10824 KB Output is correct
34 Correct 820 ms 39236 KB Output is correct
35 Correct 986 ms 26952 KB Output is correct
36 Correct 2262 ms 43240 KB Output is correct
37 Correct 1762 ms 43432 KB Output is correct
38 Correct 1689 ms 42908 KB Output is correct
39 Correct 661 ms 81016 KB Output is correct
40 Correct 2382 ms 81992 KB Output is correct
41 Correct 3780 ms 67176 KB Output is correct
42 Correct 3280 ms 52624 KB Output is correct
43 Correct 1091 ms 76836 KB Output is correct
44 Correct 467 ms 10692 KB Output is correct
45 Correct 1272 ms 35692 KB Output is correct
46 Correct 2720 ms 80932 KB Output is correct
47 Correct 2722 ms 81028 KB Output is correct
48 Correct 2662 ms 80668 KB Output is correct
49 Correct 1 ms 204 KB Output is correct