oj.uz

Submission #289785

# Submission time Handle Problem Language Result Execution time Memory
289785 2020-09-03T04:32:30 Z TMJN Game (IOI13_game) C++17
0 / 100
 2 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);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~

Subtask #1
0 / 10.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 #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 2 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 2 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 2 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -