Submission #291261

#	Time	Username	Problem	Language	Result	Execution time	Memory
291261		TMJN	Game (IOI13_game)	C++17	63 / 100	3113 ms	256004 KiB

game

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

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