oj.uz

Submission #470723

# Submission time Handle Problem Language Result Execution time Memory
470723 2021-09-05T09:14:57 Z CSQ31 Game (IOI13_game) C++17
63 / 100
 1631 ms 256004 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;
	ll val = 0;
	node(){}
	void upd(int l,int r,int pos,ll v){
		if(l==r){
			val = v;
			return;
		}
		int tm = (l+r)/2;
		if(pos<=tm){
			if(L == NULL)L = new node();
			L->upd(l,tm,pos,v);
		}
		else{
			if(R == NULL)R = new node();
			R->upd(tm+1,r,pos,v);
		}
		val = gcd2((L==NULL?0:L->val),(R==NULL?0:R->val));
	}
	ll query(int l,int r,int tl,int tr){
		if(l == tl && r == tr)return val;
		ll res = 0;
		int tm = (tl+tr)/2;
		if(l<=tm && L!=NULL)res = gcd2(res,L->query(l,min(tm,r),tl,tm));
		if(r>tm && R!=NULL)res = gcd2(res,R->query(max(l,tm+1),r,tm+1,tr));
		return res;
	}
};
struct nodex{
	nodex *L = NULL,*R = NULL;
	node * tree = NULL;
	ll val = 0;
	nodex(){tree = new node();}
}*root;
void upd2(node *a,node *b,node *c,int l,int r,int pos){
	a->val = gcd2((b==NULL?0:b->val),(c==NULL?0:c->val));
	if(l==r)return;
	int tm = (l+r)/2;
	if(pos<=tm){
		if(a->L ==  NULL)a->L = new node();
		upd2(a->L,(b==NULL?b:b->L),(c==NULL?c:c->L),l,tm,pos);
	}
	else{
		if(a->R == NULL)a->R = new node();
		upd2(a->R,(b==NULL?b:b->R),(c==NULL?c:c->R),tm+1,r,pos);
	}
}
void upd(nodex *v,int x,int y,int l,int r,ll val){
	if(l==r){ //we update this 1D segtree normally
		//cout<<"cur "<<l<<" "<<r<<" "<<y<<" "<<val<<'\n';
		v->tree->upd(1,c,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);
		}
		//cout<<"TES1"<<'\n';
		upd2(v->tree,(v->L==NULL?NULL:v->L->tree),(v->R==NULL?NULL:v->R->tree),1,c,y);
		//cout<<"TES2"<<'\n';
	}
	
}
ll query(nodex *v,int xl,int xr,int yl,int yr,int l,int r){
	if(xl == l && xr == r){
		//cout<<xl<<" "<<xr<<" "<<yl<<" "<<yr<<" "<<v->query(yl,yr,1,c)<<'\n';
		return v->tree->query(yl,yr,1,c);
	}
	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 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 292 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 332 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 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 505 ms 17408 KB Output is correct
5 Correct 369 ms 17156 KB Output is correct
6 Correct 489 ms 15044 KB Output is correct
7 Correct 533 ms 14488 KB Output is correct
8 Correct 373 ms 11076 KB Output is correct
9 Correct 567 ms 14752 KB Output is correct
10 Correct 549 ms 14284 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 296 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 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 828 ms 19960 KB Output is correct
13 Correct 1447 ms 10116 KB Output is correct
14 Correct 282 ms 5596 KB Output is correct
15 Correct 1628 ms 13224 KB Output is correct
16 Correct 588 ms 22548 KB Output is correct
17 Correct 753 ms 16460 KB Output is correct
18 Correct 1362 ms 23788 KB Output is correct
19 Correct 1165 ms 24004 KB Output is correct
20 Correct 1072 ms 23380 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 482 ms 17412 KB Output is correct
13 Correct 362 ms 17196 KB Output is correct
14 Correct 505 ms 14792 KB Output is correct
15 Correct 533 ms 14520 KB Output is correct
16 Correct 362 ms 11028 KB Output is correct
17 Correct 486 ms 14656 KB Output is correct
18 Correct 473 ms 14276 KB Output is correct
19 Correct 794 ms 19876 KB Output is correct
20 Correct 1375 ms 10296 KB Output is correct
21 Correct 274 ms 5532 KB Output is correct
22 Correct 1631 ms 13160 KB Output is correct
23 Correct 580 ms 22468 KB Output is correct
24 Correct 821 ms 16328 KB Output is correct
25 Correct 1313 ms 24008 KB Output is correct
26 Correct 1114 ms 24212 KB Output is correct
27 Correct 1052 ms 23432 KB Output is correct
28 Correct 876 ms 256000 KB Output is correct
29 Runtime error 1610 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.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 0 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 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 476 ms 17344 KB Output is correct
13 Correct 359 ms 17264 KB Output is correct
14 Correct 460 ms 14876 KB Output is correct
15 Correct 501 ms 14532 KB Output is correct
16 Correct 344 ms 11048 KB Output is correct
17 Correct 488 ms 14824 KB Output is correct
18 Correct 456 ms 14276 KB Output is correct
19 Correct 801 ms 19928 KB Output is correct
20 Correct 1365 ms 10176 KB Output is correct
21 Correct 277 ms 5524 KB Output is correct
22 Correct 1621 ms 13208 KB Output is correct
23 Correct 591 ms 22456 KB Output is correct
24 Correct 790 ms 16480 KB Output is correct
25 Correct 1280 ms 23924 KB Output is correct
26 Correct 1090 ms 24376 KB Output is correct
27 Correct 1040 ms 23672 KB Output is correct
28 Correct 893 ms 256000 KB Output is correct
29 Runtime error 1623 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -