제출 #749871

#제출 시각아이디문제언어결과실행 시간메모리
749871grogu게임 (IOI13_game)C++14
80 / 100
4057 ms256000 KiB
#include "game.h" #define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include <bits/stdc++.h> #define ld long long #define ll int #define ull unsigned long long #define llinf 100000000000000000LL // 10^17 #define iinf 2000000000 // 2*10^9 #define pb push_back #define eb emplace_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pii pair<int,int> #define pll pair<ll,ll> #define pld pair<ld,ld> #define all(a) a.begin(),a.end() #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;} #define si(a) (ll)(a.size()) using namespace std; ld gcd(ld x,ld y){ if(y>x) swap(x,y); if(y==0) return x; return gcd(y,x%y); } const ll maxx = 13000005; const ld mc = 1000000006; ll t[maxx],ls[maxx],rs[maxx],tsz = 0,root = 0; ld t2[maxx]; ld get2(ll v,ll tl,ll tr,ll l,ll r){ if(!v) return 0; if(tl>tr||tl>r||l>r||l>tr) return 0; if(tl>=l&&tr<=r) return t2[v]; ll mid = (tl+tr)/2; return gcd(get2(ls[v],tl,mid,l,r),get2(rs[v],mid+1,tr,l,r)); } ld get(ll v,ll tl,ll tr,ll l,ll r,ll x,ll y){ if(!v) return 0; if(tl>tr||tl>r||l>tr||l>r) return 0; if(tl>=l&&tr<=r) return get2(t[v],1,mc,x,y); ll mid = (tl+tr)/2; return gcd(get(ls[v],tl,mid,l,r,x,y),get(rs[v],mid+1,tr,l,r,x,y)); } void upd2(ll &v,ll tl,ll tr,ll i,ld x){ if(!v) v = ++tsz; if(tl==tr){t2[v] = x;return;} ll mid = (tl+tr)/2; if(i<=mid) upd2(ls[v],tl,mid,i,x); else upd2(rs[v],mid+1,tr,i,x); t2[v] = gcd(t2[ls[v]],t2[rs[v]]); } void upd(ll &v,ll tl,ll tr,ll x,ll y,ld val){ if(!v) v = ++tsz; if(tl==tr){upd2(t[v],1,mc,y,val);return;} ll mid = (tl+tr)/2; if(x<=mid) upd(ls[v],tl,mid,x,y,val); else upd(rs[v],mid+1,tr,x,y,val); upd2(t[v],1,mc,y,gcd(get2(t[ls[v]],1,mc,y,y),get2(t[rs[v]],1,mc,y,y))); } void init(int R, int C) { } void update(int P, int Q, long long K) { P++; Q++; upd(root,1,mc,P,Q,K); } long long calculate(int P, int Q, int U, int V) { P++; Q++; U++; V++; if(P>U) swap(U,P); if(Q>V) swap(Q,V); return get(root,1,mc,P,U,Q,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...