oj.uz

답안 #1092061

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1092061 2024-09-23T04:00:30 Z sleepntsheep 게임 (IOI13_game) C++17
0 / 100
 2 ms 456 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){if(!v)return;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(!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);
		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); }

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 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 #2
0 / 27.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 2 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 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 #5
0 / 20.0

# 결과 실행 시간 메모리 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 -