Submission #127638

#	Time	Username	Problem	Language	Result	Execution time	Memory
127638		hamzqq9	게임 (IOI13_game)	C++14	100 / 100	12584 ms	39416 KiB

game

#include "game.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define inf 1000000000
#define MOD 1000000007 
#define N 10000005
#define M 1000000
#define LOG 20
#define KOK 300
#define EPS 0.0000001
using namespace std;

struct treap {

	int key,pri;
	int l,r;
	ll val,g;

} T[N];

int root;
int go[N],l[N],r[N];
int tot_T,tot_S;

long long gcd2(long long X, long long Y) {
	if(X<Y) swap(X,Y);
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

void make2(int& node,int pos,ll val) {

	if(!node) {
	
		node=++tot_T;
		T[node].key=pos;
		T[node].pri=rand();
		T[node].l=T[node].r=0;

	}

	T[node].g=T[node].val=val;

}

void make1(int& node) {

	if(!node) node=++tot_S;

}

void relax(int root) {

	T[root].g=gcd2(gcd2(T[T[root].l].g,T[T[root].r].g),T[root].val);

}

void merge(int& root,int l,int r) {

	if(!l || !r) root=(l?l:r);
	else if(T[l].pri>T[r].pri) {

		merge(T[l].r,T[l].r,r);
		root=l;

	}
	else {

		merge(T[r].l,l,T[r].l);
		root=r;

	}

	if(root) relax(root);

}

void split(int root,int to,int& l,int& r) {

	if(!root) l=r=0;
	else if(T[root].key<=to) {

		split(T[root].r,to,T[root].r,r);
		l=root;

	}
	else {

		split(T[root].l,to,l,T[root].l);
		r=root;

	}

	if(root) relax(root);

}

ll get2(int& root,int l,int r) {

	int r1,r2,r3;

	split(root,r,r1,r3);
	split(r1,l-1,r1,r2);

	ll res=T[r2].g;

	merge(root,r1,r2);
	merge(root,root,r3);

	return res;

}

ll get1(int& node,int bas,int son,int a,int b,int c,int d) {

	if(!node) return 0;

	if(bas>=a && son<=c) return get2(go[node],b,d);

	if(orta>=a && orta+1<=c) return gcd2(get1(l[node],bas,orta,a,b,c,d),get1(r[node],orta+1,son,a,b,c,d));

	if(orta>=a) return get1(l[node],bas,orta,a,b,c,d);

	return get1(r[node],orta+1,son,a,b,c,d);

}

void up2(int& root,int pos,ll val) {

	int r1,r2,r3;

	split(root,pos,r1,r3);
	split(r1,pos-1,r1,r2);

	make2(r2,pos,val);

	merge(root,r1,r2);
	merge(root,root,r3);

}

void up1(int& node,int bas,int son,int x,int y,ll val) {

	make1(node);

	if(bas==x && son==x) {

		up2(go[node],y,val);

		return ;

	}

	if(orta>=x) up1(l[node],bas,orta,x,y,val);
	else up1(r[node],orta+1,son,x,y,val);

	ll g=gcd2(get2(go[l[node]],y,y),get2(go[r[node]],y,y));

	up2(go[node],y,g);

}

void init(int R, int C) {

	T[0].g=T[0].val=T[0].l=T[0].r=0;

	srand(time(NULL));

}

void update(int P, int Q, long long K) {

	up1(root,0,inf-1,P,Q,K);

}

long long calculate(int P, int Q, int U, int V) {

	return get1(root,0,inf-1,P,Q,U,V);

}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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