oj.uz

Submission #400264

# Submission time Handle Problem Language Result Execution time Memory
400264 2021-05-07T19:07:02 Z Jasiekstrz Game (IOI13_game) C++17
63 / 100
 3065 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;
		mkchildren();
		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);
		mkchildren();
		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 588 KB Output is correct
3 Correct 3 ms 644 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 552 KB Output is correct
10 Correct 2 ms 460 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 300 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 817 ms 38504 KB Output is correct
5 Correct 608 ms 33532 KB Output is correct
6 Correct 1074 ms 80800 KB Output is correct
7 Correct 1121 ms 80492 KB Output is correct
8 Correct 891 ms 76464 KB Output is correct
9 Correct 1027 ms 81384 KB Output is correct
10 Correct 958 ms 80120 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 296 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 668 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1032 ms 36864 KB Output is correct
13 Correct 1313 ms 16088 KB Output is correct
14 Correct 803 ms 6812 KB Output is correct
15 Correct 1504 ms 23756 KB Output is correct
16 Correct 434 ms 51268 KB Output is correct
17 Correct 2710 ms 215168 KB Output is correct
18 Correct 3065 ms 225116 KB Output is correct
19 Correct 2994 ms 225008 KB Output is correct
20 Correct 2857 ms 224160 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 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 743 ms 38480 KB Output is correct
13 Correct 504 ms 33448 KB Output is correct
14 Correct 992 ms 80680 KB Output is correct
15 Correct 998 ms 80584 KB Output is correct
16 Correct 889 ms 76512 KB Output is correct
17 Correct 1028 ms 81552 KB Output is correct
18 Correct 965 ms 80116 KB Output is correct
19 Correct 1110 ms 36900 KB Output is correct
20 Correct 1305 ms 16028 KB Output is correct
21 Correct 794 ms 6744 KB Output is correct
22 Correct 1506 ms 23768 KB Output is correct
23 Correct 429 ms 51268 KB Output is correct
24 Correct 2597 ms 215120 KB Output is correct
25 Correct 2893 ms 224932 KB Output is correct
26 Correct 2871 ms 224964 KB Output is correct
27 Correct 2919 ms 224212 KB Output is correct
28 Runtime error 436 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 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 420 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 548 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 761 ms 38480 KB Output is correct
13 Correct 508 ms 33564 KB Output is correct
14 Correct 977 ms 80652 KB Output is correct
15 Correct 990 ms 80512 KB Output is correct
16 Correct 856 ms 76740 KB Output is correct
17 Correct 990 ms 81520 KB Output is correct
18 Correct 939 ms 80136 KB Output is correct
19 Correct 1034 ms 36876 KB Output is correct
20 Correct 1287 ms 16220 KB Output is correct
21 Correct 781 ms 6724 KB Output is correct
22 Correct 1491 ms 23792 KB Output is correct
23 Correct 426 ms 51304 KB Output is correct
24 Correct 2549 ms 215132 KB Output is correct
25 Correct 2890 ms 225152 KB Output is correct
26 Correct 2868 ms 225096 KB Output is correct
27 Correct 2799 ms 224236 KB Output is correct
28 Runtime error 420 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -