oj.uz

Submission #291338

# Submission time Handle Problem Language Result Execution time Memory
291338 2020-09-05T07:17:14 Z TMJN Game (IOI13_game) C++17
63 / 100
 2946 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 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 488 KB Output is correct
11 Correct 4 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 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1345 ms 40688 KB Output is correct
5 Correct 1144 ms 41052 KB Output is correct
6 Correct 1456 ms 38032 KB Output is correct
7 Correct 1340 ms 37792 KB Output is correct
8 Correct 914 ms 24328 KB Output is correct
9 Correct 1603 ms 38032 KB Output is correct
10 Correct 1413 ms 37568 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 3 ms 640 KB Output is correct
3 Correct 5 ms 672 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 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 2075 ms 15548 KB Output is correct
13 Correct 2668 ms 6812 KB Output is correct
14 Correct 966 ms 1148 KB Output is correct
15 Correct 2940 ms 10648 KB Output is correct
16 Correct 1062 ms 18952 KB Output is correct
17 Correct 1909 ms 13452 KB Output is correct
18 Correct 2795 ms 19200 KB Output is correct
19 Correct 2487 ms 19404 KB Output is correct
20 Correct 2432 ms 18808 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 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 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 1195 ms 40696 KB Output is correct
13 Correct 1304 ms 40996 KB Output is correct
14 Correct 1241 ms 38040 KB Output is correct
15 Correct 1327 ms 37804 KB Output is correct
16 Correct 1016 ms 24224 KB Output is correct
17 Correct 1309 ms 38172 KB Output is correct
18 Correct 1305 ms 37556 KB Output is correct
19 Correct 2053 ms 15488 KB Output is correct
20 Correct 2622 ms 7008 KB Output is correct
21 Correct 1040 ms 1336 KB Output is correct
22 Correct 2946 ms 10688 KB Output is correct
23 Correct 1177 ms 19060 KB Output is correct
24 Correct 1873 ms 13648 KB Output is correct
25 Correct 2787 ms 19320 KB Output is correct
26 Correct 2420 ms 19420 KB Output is correct
27 Correct 2449 ms 18964 KB Output is correct
28 Correct 1318 ms 243576 KB Output is correct
29 Runtime error 2309 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 640 KB Output is correct
3 Correct 4 ms 512 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 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 1231 ms 41976 KB Output is correct
13 Correct 988 ms 42092 KB Output is correct
14 Correct 1219 ms 38888 KB Output is correct
15 Correct 1302 ms 38696 KB Output is correct
16 Correct 907 ms 25128 KB Output is correct
17 Correct 1327 ms 38984 KB Output is correct
18 Correct 1366 ms 38392 KB Output is correct
19 Correct 2119 ms 16364 KB Output is correct
20 Correct 2832 ms 7828 KB Output is correct
21 Correct 929 ms 2040 KB Output is correct
22 Correct 2840 ms 11384 KB Output is correct
23 Correct 1081 ms 19904 KB Output is correct
24 Correct 1940 ms 14312 KB Output is correct
25 Correct 2771 ms 20080 KB Output is correct
26 Correct 2648 ms 20352 KB Output is correct
27 Correct 2401 ms 20016 KB Output is correct
28 Correct 1272 ms 254048 KB Output is correct
29 Runtime error 2355 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -