oj.uz

Submission #400311

# Submission time Handle Problem Language Result Execution time Memory
400311 2021-05-07T20:44:32 Z Jasiekstrz Game (IOI13_game) C++17
100 / 100
 6588 ms 245156 KB 
#include<bits/stdc++.h>
#include "game.h"
using namespace std;
const int D=4;
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* son[D];
	TreeC()
	{
		val=0;
		for(int i=0;i<D;i++)
			son[i]=NULL;
	}
	~TreeC()
	{
		for(int i=0;i<D;i++)
			delete son[i];
	}
	void add(int l,int r,int x,long long c)
	{
		if(l==r)
		{
			val=c;
			return;
		}
		val=0;
		int d=(r-l+1)/D;
		for(int i=0,j=l;i<D;i++,j+=d)
		{
			if(j<=x && x<j+d)
			{
				if(son[i]==NULL)
					son[i]=new TreeC;
				son[i]->add(j,j+d-1,x,c);
			}
			val=gcd2(val, (son[i]==NULL ? 0:son[i]->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;
		long long ans=0;
		int d=(r-l+1)/D;
		for(int i=0,j=l;i<D;i++,j+=d)
			ans=gcd2(ans, (son[i]==NULL ? 0:son[i]->read(j,j+d-1,ls,rs)));
		return ans;
	}
};
struct TreeR
{
	TreeC *t;
	TreeR* son[D];
	TreeR()
	{
		t=new TreeC;
		for(int i=0;i<D;i++)
			son[i]=NULL;
	}
	~TreeR()
	{
		delete t;
		for(int i=0;i<D;i++)
			delete son[i];
	}
	void add(int l,int r,int x,int y,long long c)
	{
		if(l==r)
		{
			t->add(0,cc,y,c);
			return;
		}
		long long tmp=0;
		int d=(r-l+1)/D;
		for(int i=0,j=l;i<D;i++,j+=d)
		{
			if(j<=x && x<j+d)
			{
				if(son[i]==NULL)
					son[i]=new TreeR;
				son[i]->add(j,j+d-1,x,y,c);
			}
			tmp=gcd2(tmp, (son[i]==NULL ? 0:son[i]->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);
		long long ans=0;
		int d=(r-l+1)/D;
		for(int i=0,j=l;i<D;i++,j+=d)
			ans=gcd2(ans, (son[i]==NULL ? 0:son[i]->read(j,j+d-1,ls,rs,ly,ry)));
		return ans;
	}
};
TreeR* root;
void init(int R,int C)
{
	for(rr=1;rr<R;rr*=D);
	rr--;
	for(cc=1;cc<C;cc*=D);
	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 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 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 300 KB Output is correct
4 Correct 616 ms 8772 KB Output is correct
5 Correct 414 ms 9136 KB Output is correct
6 Correct 611 ms 5956 KB Output is correct
7 Correct 671 ms 5700 KB Output is correct
8 Correct 458 ms 4548 KB Output is correct
9 Correct 660 ms 5700 KB Output is correct
10 Correct 584 ms 5348 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 208 KB Output is correct
12 Correct 1082 ms 9624 KB Output is correct
13 Correct 2011 ms 3544 KB Output is correct
14 Correct 345 ms 840 KB Output is correct
15 Correct 2523 ms 4876 KB Output is correct
16 Correct 390 ms 8932 KB Output is correct
17 Correct 1088 ms 6224 KB Output is correct
18 Correct 1818 ms 9272 KB Output is correct
19 Correct 1641 ms 9392 KB Output is correct
20 Correct 1624 ms 8756 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 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 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 641 ms 8772 KB Output is correct
13 Correct 462 ms 9064 KB Output is correct
14 Correct 678 ms 5876 KB Output is correct
15 Correct 698 ms 5652 KB Output is correct
16 Correct 466 ms 4404 KB Output is correct
17 Correct 693 ms 5768 KB Output is correct
18 Correct 650 ms 5388 KB Output is correct
19 Correct 1095 ms 9696 KB Output is correct
20 Correct 2033 ms 3652 KB Output is correct
21 Correct 382 ms 1268 KB Output is correct
22 Correct 2574 ms 5220 KB Output is correct
23 Correct 404 ms 9260 KB Output is correct
24 Correct 1134 ms 6560 KB Output is correct
25 Correct 1895 ms 9632 KB Output is correct
26 Correct 1529 ms 9776 KB Output is correct
27 Correct 1435 ms 9176 KB Output is correct
28 Correct 795 ms 104244 KB Output is correct
29 Correct 2104 ms 116900 KB Output is correct
30 Correct 5316 ms 83408 KB Output is correct
31 Correct 5340 ms 64696 KB Output is correct
32 Correct 541 ms 3244 KB Output is correct
33 Correct 783 ms 4220 KB Output is correct
34 Correct 1014 ms 113752 KB Output is correct
35 Correct 1442 ms 60224 KB Output is correct
36 Correct 2566 ms 116228 KB Output is correct
37 Correct 2181 ms 116340 KB Output is correct
38 Correct 2127 ms 115792 KB Output is correct
39 Correct 1808 ms 90056 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 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 204 KB Output is correct
12 Correct 604 ms 10308 KB Output is correct
13 Correct 423 ms 10564 KB Output is correct
14 Correct 606 ms 7376 KB Output is correct
15 Correct 662 ms 7108 KB Output is correct
16 Correct 443 ms 5848 KB Output is correct
17 Correct 649 ms 7236 KB Output is correct
18 Correct 580 ms 6824 KB Output is correct
19 Correct 1062 ms 11204 KB Output is correct
20 Correct 1922 ms 5016 KB Output is correct
21 Correct 337 ms 2396 KB Output is correct
22 Correct 2451 ms 6272 KB Output is correct
23 Correct 401 ms 10400 KB Output is correct
24 Correct 1063 ms 7592 KB Output is correct
25 Correct 1657 ms 10704 KB Output is correct
26 Correct 1433 ms 11040 KB Output is correct
27 Correct 1438 ms 10176 KB Output is correct
28 Correct 730 ms 108236 KB Output is correct
29 Correct 1895 ms 119436 KB Output is correct
30 Correct 5098 ms 83928 KB Output is correct
31 Correct 4724 ms 64792 KB Output is correct
32 Correct 514 ms 3136 KB Output is correct
33 Correct 757 ms 4164 KB Output is correct
34 Correct 1012 ms 113988 KB Output is correct
35 Correct 1383 ms 60276 KB Output is correct
36 Correct 2525 ms 116416 KB Output is correct
37 Correct 2045 ms 116548 KB Output is correct
38 Correct 2074 ms 116036 KB Output is correct
39 Correct 1062 ms 219188 KB Output is correct
40 Correct 2926 ms 245156 KB Output is correct
41 Correct 6588 ms 173708 KB Output is correct
42 Correct 6296 ms 133184 KB Output is correct
43 Correct 1627 ms 243268 KB Output is correct
44 Correct 674 ms 3512 KB Output is correct
45 Correct 1738 ms 89212 KB Output is correct
46 Correct 3358 ms 243772 KB Output is correct
47 Correct 3323 ms 243708 KB Output is correct
48 Correct 3268 ms 243000 KB Output is correct
49 Correct 1 ms 204 KB Output is correct