Submission #1092072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092072		sleepntsheep	Game (IOI13_game)	C++17	100 / 100	3905 ms	252740 KiB

game

#include "game.h"
#include <stdlib.h>
#include <stdio.h>
#include <utility>
long long gcd2(long long X, long long Y) { return Y ? gcd2(Y, X % Y) : X; }
using pos=std::pair<int,int>;
#define N 200000
struct{int rt,l,r;}st[N*30];int ii,St;
struct{pos a;int b,l,r;long long g,gg;}tr[N*30];int jj;
void pull(int v){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,pos 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,p-1});
		split(v2,v2,v3,{q,p});
		if(v2)tr[v2].g=tr[v2].gg=k;
		else tr[v2=++jj]={{q,p},rand(),0,0,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(!v||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,2e9});
		split(v2,v2,v3,{z,2e9});
		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); }

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20