oj.uz

Submission #288436

# Submission time Handle Problem Language Result Execution time Memory
288436 2020-09-01T13:37:22 Z TMJN Game (IOI13_game) C++17
0 / 100
 57 ms 57592 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

struct node{
	long long val;
	int lx,ly,rx,ry;
	int chl,chr;
};

node tree[400000];
int c;


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 upd(int p,int q,long long k,int t){
	if(tree[t].lx<=p&&p<=tree[t].rx&&tree[t].ly<=q&&q<=tree[t].ry){
		if(tree[t].lx==tree[t].rx&&tree[t].ly==tree[t].ry){
			tree[t].val=k;
		}
		else{
			if(tree[t].chl==-1){
				if(tree[t].rx-tree[t].lx==tree[t].ry-tree[t].ly){
					tree[c]={0,tree[t].lx,tree[t].ly,(tree[t].lx+tree[t].rx)/2,tree[t].ry,-1,-1};
					tree[c+1]={0,(tree[t].lx+tree[t].rx)/2+1,tree[t].ry,tree[t].rx,tree[t].ry,-1,-1};
					tree[t].chl=c;
					tree[t].chr=c+1;
					c+=2;
				}
				else{
					tree[c]={0,tree[t].lx,tree[t].ly,tree[t].rx,(tree[t].ly+tree[t].ry)/2,-1,-1};
					tree[c+1]={0,tree[t].lx,(tree[t].ly+tree[t].ry)/2+1,tree[t].rx,tree[t].ry,-1,-1};
					tree[t].chl=c;
					tree[t].chr=c+1;
					c+=2;
				}
			}
			upd(p,q,k,tree[t].chl);
			upd(p,q,k,tree[t].chr);
			tree[t].val=gcd2(tree[tree[t].chl].val,tree[tree[t].chr].val);
		}
	}
}

long long calc(int p,int q,int u,int v,int t){
	if(t==-1)return 0;
	if(tree[t].rx<p||u<tree[t].lx||tree[t].ry<q||v<tree[t].ly)return 0;
	if(p<=tree[t].lx&&tree[t].rx<=u&&q<=tree[t].ly&&tree[t].ry<=v)return tree[t].val;
	return gcd2(calc(p,q,u,v,tree[t].chl),calc(p,q,u,v,tree[t].chr));
}

void init(int R, int C) {
	tree[0].val=0;
	tree[0].lx=tree[0].ly=0;
	tree[0].rx=tree[0].ry=(1<<30)-1;
	tree[0].chl=-1;
	tree[0].chr=-1;
	c=1;
}

void update(int P, int Q, long long K) {
	upd(P,Q,K,0);
}

long long calculate(int P, int Q, int U, int V) {
	return calc(P,Q,U,V,0);
}

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 0 ms 256 KB Output is correct
2 Runtime error 50 ms 57592 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 52 ms 57592 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Runtime error 57 ms 57592 KB Execution killed with signal 11
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 Runtime error 54 ms 57592 KB Execution killed with signal 11
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 Runtime error 55 ms 57592 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -