oj.uz

Submission #1092057

# Submission time Handle Problem Language Result Execution time Memory
1092057 2024-09-23T03:53:29 Z sleepntsheep Game (IOI13_game) C++17
0 / 100
 2 ms 600 KB 
#include "game.h"
#include <stdlib.h>
#include <stdio.h>

long long gcd2(long long X, long long Y) { return Y ? gcd2(Y, X % Y) : X; }

#define N 22500
struct{int rt,l,r;}st[N*30];int ii,St;
struct{int a,b,l,r,sz;long long g,gg;}tr[N*30];int jj;
void pull(int v){tr[v].sz=1+tr[tr[v].l].sz+tr[tr[v].r].sz;tr[v].gg=gcd2(tr[v].g,gcd2(tr[tr[v].l].gg,tr[tr[v].r].gg));}
void merge(int&v,int l,int r){
	if(!l||!r)return void(v=l^r);
	if(tr[l].b<tr[r].b) merge(tr[r].l,l,tr[r].l),v=r;
	else merge(tr[l].r,tr[l].r,r),v=l;
	pull(v);
}
void split(int v,int&l,int&r,int p){
	if(!v)return void(l=r=0);
	if(tr[v].a<=p)split(tr[v].r,tr[v].r,r,p),l=v;
	else split(tr[v].l,l,tr[v].l,p),r=v;
	pull(v);
}

void upd(int&v,int l,int r,int p,int q,long long k){
	if(!v)v=++ii;
	{
		int v1,v2,v3;
		split(st[v].rt,v1,v2,q-1);
		split(v2,v2,v3,q);
		if(v2)tr[v2].g=tr[v2].gg=k;
		else v2=++jj;tr[v2]={q,rand(),0,0,1,k,k};
		merge(v1,v1,v2);
		merge(st[v].rt,v1,v3);
	}
	if(l==r)return;
	if(p<=(l+r)/2)upd(st[v].l,l,(l+r)/2,p,q,k);
	else upd(st[v].r,(l+r)/2+1,r,p,q,k);
}

long long qry(int v,int l,int r,int x,int y,int w,int z){
	if(r<x||y<l)return 0;
	if(x<=l&&r<=y){
		int v1,v2,v3;long long zz;
		split(st[v].rt,v1,v2,w-1);
		split(v2,v2,v3,z);
		zz=tr[v2].gg;
		merge(v2,v2,v3);
		merge(st[v].rt,v1,v2);
		return zz;
	}
	return gcd2(qry(st[v].l,l,(l+r)/2,x,y,w,z),qry(st[v].r,(l+r)/2+1,r,x,y,w,z));
}

void init(int R, int C) { }
void update(int P, int Q, long long K) { upd(St,0,1e9,P,Q,K); }
long long calculate(int P, int Q, int U, int V) { return qry(St,0,1e9,P,U,Q,V); }

Compilation message

game.cpp: In function 'void upd(int&, int, int, int, int, long long int)':
game.cpp:31:3: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   31 |   else v2=++jj;tr[v2]={q,rand(),0,0,1,k,k};
      |   ^~~~
game.cpp:31:16: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   31 |   else v2=++jj;tr[v2]={q,rand(),0,0,1,k,k};
      |                ^~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #5
0 / 20.0

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