oj.uz

Submission #291256

# Submission time Handle Problem Language Result Execution time Memory
291256 2020-09-05T01:24:23 Z TMJN Game (IOI13_game) C++14
63 / 100
 3001 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 1 ms 384 KB Output is correct
2 Correct 5 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 1 ms 384 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 3 ms 640 KB Output is correct
10 Correct 1 ms 512 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 1 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 1198 ms 40952 KB Output is correct
5 Correct 1071 ms 41224 KB Output is correct
6 Correct 1248 ms 38192 KB Output is correct
7 Correct 1270 ms 38012 KB Output is correct
8 Correct 834 ms 24440 KB Output is correct
9 Correct 1405 ms 38216 KB Output is correct
10 Correct 1246 ms 37752 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 4 ms 632 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 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 3 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 2231 ms 15872 KB Output is correct
13 Correct 2802 ms 7256 KB Output is correct
14 Correct 1193 ms 1528 KB Output is correct
15 Correct 2852 ms 11064 KB Output is correct
16 Correct 1136 ms 19316 KB Output is correct
17 Correct 2112 ms 13932 KB Output is correct
18 Correct 2871 ms 19536 KB Output is correct
19 Correct 2479 ms 19752 KB Output is correct
20 Correct 2472 ms 19112 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 1 ms 384 KB Output is correct
2 Correct 3 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 384 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 3 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 1206 ms 40656 KB Output is correct
13 Correct 1061 ms 40952 KB Output is correct
14 Correct 1262 ms 38012 KB Output is correct
15 Correct 1322 ms 37744 KB Output is correct
16 Correct 908 ms 24276 KB Output is correct
17 Correct 1258 ms 38008 KB Output is correct
18 Correct 1263 ms 37752 KB Output is correct
19 Correct 2088 ms 15424 KB Output is correct
20 Correct 2588 ms 6892 KB Output is correct
21 Correct 933 ms 1152 KB Output is correct
22 Correct 2784 ms 10492 KB Output is correct
23 Correct 1058 ms 18940 KB Output is correct
24 Correct 1963 ms 13508 KB Output is correct
25 Correct 3001 ms 19264 KB Output is correct
26 Correct 2595 ms 19320 KB Output is correct
27 Correct 2328 ms 18716 KB Output is correct
28 Correct 1264 ms 243620 KB Output is correct
29 Runtime error 2226 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 2 ms 384 KB Output is correct
2 Correct 3 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 0 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 3 ms 640 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1257 ms 40756 KB Output is correct
13 Correct 986 ms 40996 KB Output is correct
14 Correct 1212 ms 38048 KB Output is correct
15 Correct 1279 ms 37816 KB Output is correct
16 Correct 868 ms 24312 KB Output is correct
17 Correct 1403 ms 38272 KB Output is correct
18 Correct 1242 ms 37540 KB Output is correct
19 Correct 2081 ms 15488 KB Output is correct
20 Correct 2590 ms 6812 KB Output is correct
21 Correct 1079 ms 1136 KB Output is correct
22 Correct 2922 ms 10516 KB Output is correct
23 Correct 1004 ms 18960 KB Output is correct
24 Correct 1766 ms 13408 KB Output is correct
25 Correct 2675 ms 19196 KB Output is correct
26 Correct 2713 ms 19420 KB Output is correct
27 Correct 2600 ms 18672 KB Output is correct
28 Correct 1352 ms 243544 KB Output is correct
29 Runtime error 2582 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -