oj.uz

Submission #291261

# Submission time Handle Problem Language Result Execution time Memory
291261 2020-09-05T01:57:28 Z TMJN Game (IOI13_game) C++17
63 / 100
 3113 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[50000000];

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

Compilation message

grader.c: In function 'int main()':
grader.c:25:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   25 |     while(res != 1);
      |     ^~~~~
grader.c:26:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   26 |  res = fscanf(f, "%d", &C);
      |  ^~~
grader.c:27:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   27 |     while(res != 1);
      |     ^~~~~
grader.c:28:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   28 |  res = fscanf(f, "%d", &N);
      |  ^~~

Subtask #1
10.0 / 10.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 5 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 3 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 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1283 ms 40696 KB Output is correct
5 Correct 1044 ms 40964 KB Output is correct
6 Correct 1218 ms 37952 KB Output is correct
7 Correct 1399 ms 37752 KB Output is correct
8 Correct 863 ms 24224 KB Output is correct
9 Correct 1310 ms 38008 KB Output is correct
10 Correct 1321 ms 37516 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 1 ms 384 KB Output is correct
2 Correct 4 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 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 3 ms 384 KB Output is correct
12 Correct 2154 ms 15444 KB Output is correct
13 Correct 2771 ms 6904 KB Output is correct
14 Correct 922 ms 1144 KB Output is correct
15 Correct 2854 ms 10500 KB Output is correct
16 Correct 1027 ms 18868 KB Output is correct
17 Correct 1818 ms 13432 KB Output is correct
18 Correct 3113 ms 19256 KB Output is correct
19 Correct 2608 ms 19512 KB Output is correct
20 Correct 2582 ms 18688 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 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 5 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 1267 ms 40876 KB Output is correct
13 Correct 1099 ms 41208 KB Output is correct
14 Correct 1239 ms 38136 KB Output is correct
15 Correct 1499 ms 37940 KB Output is correct
16 Correct 848 ms 24508 KB Output is correct
17 Correct 1358 ms 38292 KB Output is correct
18 Correct 1331 ms 37600 KB Output is correct
19 Correct 2043 ms 15684 KB Output is correct
20 Correct 2797 ms 7024 KB Output is correct
21 Correct 979 ms 1208 KB Output is correct
22 Correct 3096 ms 10696 KB Output is correct
23 Correct 1043 ms 18936 KB Output is correct
24 Correct 1819 ms 13512 KB Output is correct
25 Correct 2793 ms 19156 KB Output is correct
26 Correct 2449 ms 19428 KB Output is correct
27 Correct 2394 ms 18776 KB Output is correct
28 Correct 1343 ms 243756 KB Output is correct
29 Runtime error 2336 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 4 ms 672 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 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 1190 ms 40700 KB Output is correct
13 Correct 1000 ms 40952 KB Output is correct
14 Correct 1427 ms 38084 KB Output is correct
15 Correct 1474 ms 37708 KB Output is correct
16 Correct 985 ms 24456 KB Output is correct
17 Correct 1282 ms 38024 KB Output is correct
18 Correct 1207 ms 37636 KB Output is correct
19 Correct 1994 ms 15456 KB Output is correct
20 Correct 2532 ms 6832 KB Output is correct
21 Correct 937 ms 1148 KB Output is correct
22 Correct 2937 ms 10592 KB Output is correct
23 Correct 1028 ms 18928 KB Output is correct
24 Correct 1877 ms 13664 KB Output is correct
25 Correct 2864 ms 19296 KB Output is correct
26 Correct 2558 ms 19452 KB Output is correct
27 Correct 2519 ms 18740 KB Output is correct
28 Correct 1166 ms 243572 KB Output is correct
29 Runtime error 2171 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -