Submission #288436

#	Time	Username	Problem	Language	Result	Execution time	Memory
288436		TMJN	Game (IOI13_game)	C++17	0 / 100	57 ms	57592 KiB

game

#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 (stderr)

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
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20