제출 #1012964

#제출 시각아이디문제언어결과실행 시간메모리
1012964pcc게임 (IOI13_game)C++17
63 / 100
751 ms150612 KiB
#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); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...