oj.uz

Submission #291251

# Submission time Handle Problem Language Result Execution time Memory
291251 2020-09-05T00:33:32 Z TMJN Game (IOI13_game) C++17
0 / 100
 4 ms 640 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 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;
    		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);
    }
     
    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++;
    	}
    	updy(treex[k].chy,0,(1<<30)-1,y,val);
    	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;
    	}
    	updx(treex[k].chl,l,(l+r)/2,x,y,val);
    	updx(treex[k].chr,(l+r)/2+1,r,x,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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 3 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 4 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 2 ms 640 KB Output isn't correct
3 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 Incorrect 3 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -