제출 #1012964

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1012964		pcc	게임 (IOI13_game)	C++17	63 / 100	751 ms	150612 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

inline 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;
}

int R,C;
const int mxn = 3e4+10;
const int LEN1 = 4e6+10;
const int LEN2 = mxn*30;

struct SEG2D{
	struct node{
		ll val;
		int pl,pr;
		node(){
			val = pl = pr = 0;
		}
	};
	struct node2d{
		int val;
		int pl,pr;
		node2d(){
			val = pl = pr = 0;
		}
	};
	node seg[LEN1];
	node2d seg2[LEN2];
	int ptr = 0,ptr2 = 0;
	SEG2D(){}
	int newnode(){
		ptr++;
		assert(ptr<LEN1);
		return ptr;
	}
	int newnode2(){
		ptr2++;
		assert(ptr2<LEN2);
		return ptr2;
	}
	int modify(int now,int l,int r,int p,ll v,int pul,int pur){
		if(!now)now = newnode();
		if(l == r){
			if(v >= 0)seg[now].val = v;
			else seg[now].val = gcd2(seg[pul].val,seg[pur].val);
			return now;
		}
		int mid = (l+r)>>1;
		if(mid>=p)seg[now].pl = modify(seg[now].pl,l,mid,p,v,seg[pul].pl,seg[pur].pl);
		else seg[now].pr = modify(seg[now].pr,mid+1,r,p,v,seg[pul].pr,seg[pur].pr);
		int ls = seg[now].pl,rs = seg[now].pr;
		seg[now].val = gcd2(seg[ls].val,seg[rs].val);
		return now;
	}
	ll getval(int now,int l,int r,int s,int e){
		if(!now)return 0ll;
		if(l>=s&&e>=r)return seg[now].val;
		int mid = (l+r)>>1;
		if(mid>=e)return getval(seg[now].pl,l,mid,s,e);
		else if(mid<s)return getval(seg[now].pr,mid+1,r,s,e);
		else return gcd2(getval(seg[now].pl,l,mid,s,e),getval(seg[now].pr,mid+1,r,s,e));
	}
	int modify2(int now,int l,int r,int row,int col,ll v){
		if(!now)now = newnode2();
		if(l == r){
			seg2[now].val = modify(seg2[now].val,0,C,col,v,0,0);
			//cerr<<"SEG2D:"<<' '<<l<<' '<<r<<' '<<seg[seg2[now].val].val<<endl;
			return now;
		}
		int mid = (l+r)>>1;
		if(mid>=row)seg2[now].pl = modify2(seg2[now].pl,l,mid,row,col,v);
		else seg2[now].pr = modify2(seg2[now].pr,mid+1,r,row,col,v);
		seg2[now].val = modify(seg2[now].val,0,C,col,-1,seg2[seg2[now].pl].val,seg2[seg2[now].pr].val);
		//cerr<<"SEG2D:"<<' '<<l<<' '<<r<<' '<<seg[seg2[now].val].val<<endl;
		return now;
	}
	ll getval2(int now,int l,int r,int sr,int sc,int er,int ec){
		if(!now)return 0ll;
		if(l>=sr&&er>=r){
			//cerr<<"GETVAL: "<<l<<' '<<r<<' '<<getval(seg2[now].val,0,C,sc,ec)<<endl;
			return getval(seg2[now].val,0,C,sc,ec);
		}
		int mid = (l+r)>>1;
		if(mid>=er)return getval2(seg2[now].pl,l,mid,sr,sc,er,ec);
		else if(mid<sr)return getval2(seg2[now].pr,mid+1,r,sr,sc,er,ec);
		else return gcd2(getval2(seg2[now].pl,l,mid,sr,sc,er,ec),getval2(seg2[now].pr,mid+1,r,sr,sc,er,ec));
	}
};

SEG2D seg;
int rt;

void init(int RR, int CC) {
	R = RR,C = CC;
	//cerr<<"INIT!"<<" "<<R<<' '<<C<<endl;
	rt = seg.newnode2();
	//cerr<<"INIT!"<<endl;
}

void update(int P, int Q, long long K) {
	//cerr<<"UPDATE: "<<P<<' '<<Q<<' '<<K<<endl;
	rt = seg.modify2(rt,0,R,P,Q,K);
	//cerr<<"UPDATE DONE!"<<endl;
}

long long calculate(int P, int Q, int U, int V) {
	//cerr<<"CALC: "<<P<<' '<<Q<<' '<<U<<' '<<V<<endl;
	return seg.getval2(rt,0,R,P,Q,U,V);
}

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