oj.uz

Submission #400269

# Submission time Handle Problem Language Result Execution time Memory
400269 2021-05-07T19:10:07 Z Jasiekstrz Game (IOI13_game) C++17
63 / 100
 1689 ms 256004 KB 
#include<bits/stdc++.h>
#include "game.h"
using namespace std;
long long gcd2(long long X,long long Y) 
{
    long long tmp;
    while(X!=Y && Y!=0)
	{
        tmp=X;
        X=Y;
        Y=tmp%Y;
    }
    return X;
}
int rr,cc;
struct TreeC
{
	long long val;
	TreeC *lson,*rson;
	TreeC()
	{
		val=0;
		lson=NULL;
		rson=NULL;
	}
	~TreeC()
	{
		delete lson;
		delete rson;
	}
	void mkchildren()
	{
		if(lson==NULL)
			lson=new TreeC;
		if(rson==NULL)
			rson=new TreeC;
		return;
	}
	void add(int l,int r,int x,long long c)
	{
		if(l==r)
		{
			val=c;
			return;
		}
		mkchildren();
		int mid=(l+r)/2;
		if(x<=mid)
			lson->add(l,mid,x,c);
		else
			rson->add(mid+1,r,x,c);
		val=gcd2(lson->val,rson->val);
		return;
	}
	long long read(int l,int r,int ls,int rs)
	{
		if(rs<l || r<ls)
			return 0;
		if(ls<=l && r<=rs)
			return val;
		if(lson==NULL)
			return 0;
		int mid=(l+r)/2;
		return gcd2(lson->read(l,mid,ls,rs),rson->read(mid+1,r,ls,rs));
	}
};
struct TreeR
{
	TreeC *t;
	TreeR *lson,*rson;
	TreeR()
	{
		t=new TreeC;
		lson=NULL;
		rson=NULL;
	}
	~TreeR()
	{
		delete t;
		delete lson;
		delete rson;
	}
	void mkchildren()
	{
		if(lson==NULL)
			lson=new TreeR;
		if(rson==NULL)
			rson=new TreeR;
		return;
	}
	void add(int l,int r,int x,int y,long long c)
	{
		if(l==r)
		{
			t->add(0,cc,y,c);
			return;
		}
		int mid=(l+r)/2;
		mkchildren();
		if(x<=mid)
			lson->add(l,mid,x,y,c);
		else
			rson->add(mid+1,r,x,y,c);
		long long tmp=gcd2(lson->t->read(0,cc,y,y),rson->t->read(0,cc,y,y));
		t->add(0,cc,y,tmp);
		return;
	}
	long long read(int l,int r,int ls,int rs,int ly,int ry)
	{
		if(rs<l || r<ls)
			return 0;
		if(ls<=l && r<=rs)
			return t->read(0,cc,ly,ry);
		if(lson==NULL)
			return 0;
		int mid=(l+r)/2;
		return gcd2(lson->read(l,mid,ls,rs,ly,ry),rson->read(mid+1,r,ls,rs,ly,ry));
	}
};
TreeR* root;
void init(int R,int C)
{
	for(rr=1;rr<R;rr*=2);
	rr--;
	for(cc=1;cc<C;cc*=2);
	cc--;
	root=new TreeR;
	return;
}
void update(int P,int Q,long long K)
{
	root->add(0,rr,P,Q,K);
	return;
}
long long calculate(int P,int Q,int U,int V)
{
	return root->read(0,rr,P,U,Q,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 460 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 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 494 ms 19644 KB Output is correct
5 Correct 403 ms 20108 KB Output is correct
6 Correct 521 ms 17064 KB Output is correct
7 Correct 585 ms 16864 KB Output is correct
8 Correct 382 ms 11076 KB Output is correct
9 Correct 561 ms 17084 KB Output is correct
10 Correct 537 ms 16612 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 2 ms 460 KB Output is correct
3 Correct 2 ms 460 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 460 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 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 823 ms 22468 KB Output is correct
13 Correct 1251 ms 8796 KB Output is correct
14 Correct 310 ms 1012 KB Output is correct
15 Correct 1495 ms 13136 KB Output is correct
16 Correct 378 ms 29516 KB Output is correct
17 Correct 888 ms 18212 KB Output is correct
18 Correct 1689 ms 29752 KB Output is correct
19 Correct 1297 ms 30096 KB Output is correct
20 Correct 1219 ms 29340 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 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 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 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 483 ms 19676 KB Output is correct
13 Correct 363 ms 20136 KB Output is correct
14 Correct 535 ms 17076 KB Output is correct
15 Correct 577 ms 16836 KB Output is correct
16 Correct 374 ms 10948 KB Output is correct
17 Correct 570 ms 17048 KB Output is correct
18 Correct 526 ms 16660 KB Output is correct
19 Correct 838 ms 22468 KB Output is correct
20 Correct 1249 ms 8900 KB Output is correct
21 Correct 312 ms 964 KB Output is correct
22 Correct 1439 ms 13292 KB Output is correct
23 Correct 378 ms 29508 KB Output is correct
24 Correct 910 ms 18200 KB Output is correct
25 Correct 1544 ms 29888 KB Output is correct
26 Correct 1321 ms 30076 KB Output is correct
27 Correct 1247 ms 29300 KB Output is correct
28 Runtime error 613 ms 256004 KB Execution killed with signal 9
29 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 2 ms 460 KB Output is correct
3 Correct 2 ms 460 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 460 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 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 488 ms 19656 KB Output is correct
13 Correct 365 ms 19932 KB Output is correct
14 Correct 523 ms 17096 KB Output is correct
15 Correct 585 ms 16964 KB Output is correct
16 Correct 379 ms 10948 KB Output is correct
17 Correct 565 ms 16992 KB Output is correct
18 Correct 536 ms 16520 KB Output is correct
19 Correct 820 ms 22464 KB Output is correct
20 Correct 1242 ms 8748 KB Output is correct
21 Correct 317 ms 1092 KB Output is correct
22 Correct 1430 ms 13248 KB Output is correct
23 Correct 367 ms 29708 KB Output is correct
24 Correct 892 ms 18244 KB Output is correct
25 Correct 1491 ms 29764 KB Output is correct
26 Correct 1324 ms 30096 KB Output is correct
27 Correct 1279 ms 29332 KB Output is correct
28 Runtime error 609 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -