Submission #384158

#TimeUsernameProblemLanguageResultExecution timeMemory
384158alishahali1382Game (IOI13_game)C++14
63 / 100
1700 ms236652 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define debug(x) {cerr<<#x<<"="<<x<<"\n";} #define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";} #define debugp(p) {cerr<<#p" = {"<<p.first<<", "<<p.second<<"}\n";} #define pb push_back #define all(x) x.begin(), x.end() ll gcd2(ll X, ll Y) { ll tmp; while (X != Y && Y != 0) { tmp = X; X = Y; Y = tmp % Y; } return X; } const int SEGSZ=7000000, SEGSZ2=300000; ll seg[SEGSZ], ans; int L[SEGSZ], R[SEGSZ], ts; int Set(int id, int tl, int tr, int pos, ll val){ if (!id) id=++ts; if (tr-tl==1){ seg[id]=val; return id; } int mid=(tl+tr)>>1; if (pos<mid) L[id]=Set(L[id], tl, mid, pos, val); else R[id]=Set(R[id], mid, tr, pos, val); seg[id]=gcd2(seg[L[id]], seg[R[id]]); return id; } void Get(int id, int tl, int tr, int l, int r, ll &ans){ if (r<=tl || tr<=l || !id) return ; if (l<=tl && tr<=r){ // debug(seg[id]) ans=gcd2(ans, seg[id]); // overall log(10^18) for single query of problem return ; } int mid=(tl+tr)>>1; Get(L[id], tl, mid, l, r, ans); Get(R[id], mid, tr, l, r, ans); } int n, m, root; int seg2[SEGSZ2], L2[SEGSZ2], R2[SEGSZ2], ts2; int Set2(int id, int tl, int tr, int x, int y, ll val){ if (!id) id=++ts2; // cerr<<"update "<<val<<" in "<<tl<<" "<<tr<<"\n"; if (tr-tl==1) { seg2[id]=Set(seg2[id], 0, m, y, val); return id; } int mid=(tl+tr)>>1; if (x<mid) L2[id]=Set2(L2[id], tl, mid, x, y, val); else R2[id]=Set2(R2[id], mid, tr, x, y, val); // debug2(L2[id], R2[id]) // debug2(seg[seg2[L2[id]]], seg[seg2[R2[id]]]) ll res=0; Get(seg2[L2[id]], 0, m, y, y+1, res); Get(seg2[R2[id]], 0, m, y, y+1, res); // debug(res) seg2[id]=Set(seg2[id], 0, m, y, res); return id; } void Get2(int id, int tl, int tr, int l1, int l2, int r1, int r2){ if (r1<=tl || tr<=l1 || !id) return ; if (l1<=tl && tr<=r1){ // debug2(tl, tr) Get(seg2[id], 0, m, l2, r2, ans); return ; } int mid=(tl+tr)>>1; Get2(L2[id], tl, mid, l1, l2, r1, r2); Get2(R2[id], mid, tr, l1, l2, r1, r2); } void init(int nn, int mm) { n=nn; m=mm; } void update(int P, int Q, ll K) { root=Set2(root, 0, n, P, Q, K); } ll calculate(int P, int Q, int U, int V) { ans=0; Get2(root, 0, n, P, Q, U+1, V+1); return ans; } /* 3 3 4 2 0 1 2 2 1 1 0 13 1 2 2 1 2 0 0 2 2 */
#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...