oj.uz

Submission #400284

# Submission time Handle Problem Language Result Execution time Memory
400284 2021-05-07T19:23:24 Z Jasiekstrz Game (IOI13_game) C++17
63 / 100
 1817 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 add(int l,int r,int x,long long c)
	{
		if(l==r)
		{
			val=c;
			return;
		}
		int mid=(l+r)/2;
		if(x<=mid)
		{
			if(lson==NULL)
				lson=new TreeC;
			lson->add(l,mid,x,c);
		}
		else
		{
			if(rson==NULL)
				rson=new TreeC;
			rson->add(mid+1,r,x,c);
		}
		val=gcd2((lson==NULL ? 0:lson->val), (rson==NULL ? 0: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;
		int mid=(l+r)/2;
		return gcd2((lson==NULL ? 0:lson->read(l,mid,ls,rs)),
		   	(rson==NULL ? 0: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 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;
		if(x<=mid)
		{
			if(lson==NULL)
				lson=new TreeR;
			lson->add(l,mid,x,y,c);
		}
		else
		{
			if(rson==NULL)
				rson=new TreeR;
			rson->add(mid+1,r,x,y,c);
		}
		long long tmp=gcd2((lson==NULL ? 0:lson->t->read(0,cc,y,y)),
				(rson==NULL ? 0: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);
		int mid=(l+r)/2;
		return gcd2((lson==NULL ? 0:lson->read(l,mid,ls,rs,ly,ry)),
				(rson==NULL ? 0: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 332 KB Output is correct
3 Correct 2 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 2 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 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 516 ms 13424 KB Output is correct
5 Correct 371 ms 13832 KB Output is correct
6 Correct 503 ms 10692 KB Output is correct
7 Correct 545 ms 10420 KB Output is correct
8 Correct 374 ms 7268 KB Output is correct
9 Correct 539 ms 10692 KB Output is correct
10 Correct 506 ms 10180 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 2 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 907 ms 15908 KB Output is correct
13 Correct 1477 ms 6252 KB Output is correct
14 Correct 300 ms 928 KB Output is correct
15 Correct 1604 ms 8728 KB Output is correct
16 Correct 358 ms 18300 KB Output is correct
17 Correct 890 ms 11388 KB Output is correct
18 Correct 1434 ms 18476 KB Output is correct
19 Correct 1226 ms 18760 KB Output is correct
20 Correct 1167 ms 18136 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 1 ms 332 KB Output is correct
3 Correct 2 ms 336 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 336 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 524 ms 13532 KB Output is correct
13 Correct 360 ms 13804 KB Output is correct
14 Correct 503 ms 10788 KB Output is correct
15 Correct 549 ms 10448 KB Output is correct
16 Correct 364 ms 7108 KB Output is correct
17 Correct 552 ms 10656 KB Output is correct
18 Correct 515 ms 10180 KB Output is correct
19 Correct 924 ms 15876 KB Output is correct
20 Correct 1434 ms 6140 KB Output is correct
21 Correct 307 ms 1012 KB Output is correct
22 Correct 1568 ms 8928 KB Output is correct
23 Correct 351 ms 18244 KB Output is correct
24 Correct 832 ms 11432 KB Output is correct
25 Correct 1504 ms 18576 KB Output is correct
26 Correct 1206 ms 18756 KB Output is correct
27 Correct 1214 ms 18024 KB Output is correct
28 Correct 1018 ms 256000 KB Output is correct
29 Runtime error 1817 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 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 522 ms 13524 KB Output is correct
13 Correct 365 ms 14020 KB Output is correct
14 Correct 492 ms 10692 KB Output is correct
15 Correct 533 ms 10432 KB Output is correct
16 Correct 374 ms 7224 KB Output is correct
17 Correct 525 ms 10564 KB Output is correct
18 Correct 503 ms 10192 KB Output is correct
19 Correct 918 ms 15764 KB Output is correct
20 Correct 1392 ms 6244 KB Output is correct
21 Correct 310 ms 936 KB Output is correct
22 Correct 1583 ms 8908 KB Output is correct
23 Correct 348 ms 18228 KB Output is correct
24 Correct 821 ms 11468 KB Output is correct
25 Correct 1396 ms 18632 KB Output is correct
26 Correct 1208 ms 18720 KB Output is correct
27 Correct 1159 ms 18244 KB Output is correct
28 Correct 1057 ms 256000 KB Output is correct
29 Runtime error 1811 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -