oj.uz

Submission #291250

# Submission time Handle Problem Language Result Execution time Memory
291250 2020-09-05T00:30:37 Z TMJN Game (IOI13_game) C++17
63 / 100
 3429 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;


struct nodex{
	int chl,chr,chy;
};

struct nodey{
	long long val;
	int chl,chr;
};

nodex treex[700000];
nodey treey[20000000];

int cx,cy;

long long calcx(int k,int l,int r,int lx,int rx,int ly,int ry);

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;
}

void init(int R, int C) {
	cx=1;
	treex[0]={-1,-1,-1};
}

void updy(int k,int l,int r,int y,long long val){
	if(r<y||y<l)return;
	if(l==r){
		treey[k].val=val;
//		cout<<k<<' '<<l<<' '<<r<<' '<<y<<' '<<val<<' '<<treey[k].val<<endl;
		return;
	}
	if(treey[k].chl==-1){
		treey[k].chl=cy;
		treey[k].chr=cy+1;
		treey[cy]={0,-1,-1};
		treey[cy+1]={0,-1,-1};
		cy+=2;
	}
	updy(treey[k].chl,l,(l+r)/2,y,val);
	updy(treey[k].chr,(l+r)/2+1,r,y,val);
	treey[k].val=gcd2(treey[treey[k].chl].val,treey[treey[k].chr].val);
//	cout<<k<<' '<<l<<' '<<r<<' '<<y<<' '<<val<<' '<<treey[k].val<<endl;
}

void updx(int k,int l,int r,int x,int y,long long val){
	if(k==-1||r<x||x<l)return;
	if(treex[k].chy==-1){
		treex[k].chy=cy;
		treey[cy]={0,-1,-1};
		cy++;
	}
	if(l!=r&&treex[k].chl==-1){
		treex[k].chl=cx;
		treex[k].chr=cx+1;
		treex[cx]={-1,-1,-1};
		treex[cx+1]={-1,-1,-1};
		cx+=2;
	}
	if(l!=r){
		updx(treex[k].chl,l,(l+r)/2,x,y,val);
		updx(treex[k].chr,(l+r)/2+1,r,x,y,val);
		updy(treex[k].chy,0,(1<<30)-1,y,gcd2(calcx(treex[k].chl,l,(l+r)/2,l,r,y,y),calcx(treex[k].chr,(l+r)/2+1,r,l,r,y,y)));
	}
	else{
		updy(treex[k].chy,0,(1<<30)-1,y,val);
	}
}

void update(int P, int Q, long long K) {
	updx(0,0,(1<<30)-1,P,Q,K);
}

long long calcy(int k,int l,int r,int ly,int ry){
	if(k==-1||r<ly||ry<l)return 0;
	else if(ly<=l&&r<=ry)return treey[k].val;
	else return gcd2(calcy(treey[k].chl,l,(l+r)/2,ly,ry),calcy(treey[k].chr,(l+r)/2+1,r,ly,ry));
}

long long calcx(int k,int l,int r,int lx,int rx,int ly,int ry){
	if(k==-1||r<lx||rx<l)return 0;
	else if(lx<=l&&r<=rx){
		return calcy(treex[k].chy,0,(1<<30)-1,ly,ry);
	}
	else return gcd2(calcx(treex[k].chl,l,(l+r)/2,lx,rx,ly,ry),calcx(treex[k].chr,(l+r)/2+1,r,lx,rx,ly,ry));
}

long long calculate(int P, int Q, int U, int V) {
	return calcx(0,0,(1<<30)-1,P,U,Q,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 2 ms 544 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 1 ms 416 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1409 ms 40788 KB Output is correct
5 Correct 1010 ms 41052 KB Output is correct
6 Correct 1203 ms 37996 KB Output is correct
7 Correct 1274 ms 37828 KB Output is correct
8 Correct 916 ms 24272 KB Output is correct
9 Correct 1397 ms 38008 KB Output is correct
10 Correct 1244 ms 37496 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2016 ms 15744 KB Output is correct
13 Correct 2686 ms 6944 KB Output is correct
14 Correct 1046 ms 1176 KB Output is correct
15 Correct 2868 ms 10548 KB Output is correct
16 Correct 1031 ms 18936 KB Output is correct
17 Correct 1845 ms 13432 KB Output is correct
18 Correct 2689 ms 19196 KB Output is correct
19 Correct 2416 ms 19344 KB Output is correct
20 Correct 2563 ms 18692 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1236 ms 40908 KB Output is correct
13 Correct 988 ms 40988 KB Output is correct
14 Correct 1238 ms 38048 KB Output is correct
15 Correct 1300 ms 37804 KB Output is correct
16 Correct 1030 ms 24320 KB Output is correct
17 Correct 1354 ms 38024 KB Output is correct
18 Correct 1201 ms 37624 KB Output is correct
19 Correct 2004 ms 15428 KB Output is correct
20 Correct 2632 ms 6880 KB Output is correct
21 Correct 895 ms 1096 KB Output is correct
22 Correct 2883 ms 10516 KB Output is correct
23 Correct 1042 ms 18936 KB Output is correct
24 Correct 1791 ms 13532 KB Output is correct
25 Correct 2655 ms 19240 KB Output is correct
26 Correct 2432 ms 19388 KB Output is correct
27 Correct 2356 ms 18748 KB Output is correct
28 Correct 1189 ms 243552 KB Output is correct
29 Runtime error 2138 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 384 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 416 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 2 ms 544 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1427 ms 40732 KB Output is correct
13 Correct 1027 ms 41000 KB Output is correct
14 Correct 1298 ms 38068 KB Output is correct
15 Correct 1242 ms 37712 KB Output is correct
16 Correct 867 ms 24312 KB Output is correct
17 Correct 1289 ms 38016 KB Output is correct
18 Correct 1253 ms 37548 KB Output is correct
19 Correct 2068 ms 15412 KB Output is correct
20 Correct 2753 ms 7016 KB Output is correct
21 Correct 1039 ms 1156 KB Output is correct
22 Correct 3429 ms 10908 KB Output is correct
23 Correct 1374 ms 19320 KB Output is correct
24 Correct 1866 ms 14072 KB Output is correct
25 Correct 2774 ms 19820 KB Output is correct
26 Correct 2460 ms 20556 KB Output is correct
27 Correct 2338 ms 19808 KB Output is correct
28 Correct 1181 ms 244088 KB Output is correct
29 Runtime error 2295 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -