Submission #123774

#TimeUsernameProblemLanguageResultExecution timeMemory
123774Mahdi_JfriGame (IOI13_game)C++14
0 / 100
2 ms376 KiB
#include "game.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int maxn = 1e4 + 20; const int maxb = 15; const int sq = 100000001; int sz; int x[maxn] , y[maxn] , tmp[maxn] , seg[maxb][maxn]; ll g[maxb][maxn * 4] , val[maxn]; vector<int> cmpx; bool cmpy(int a , int b) { return y[a] < y[b]; } void build(int s = 0 , int e = cmpx.size() , int h = 0) { if(e - s < 2) { seg[h][s] = tmp[s]; return; } int m = (s + e) / 2; build(s , m , h + 1); build(m , e , h + 1); merge(seg[h + 1] + s , seg[h + 1] + m , seg[h + 1] + m , seg[h + 1] + e , seg[h] + s , cmpy); } void buildgcd(int h , int s = 0 , int e = cmpx.size() , int v = 1) { if(e - s < 2) { g[h][v] = val[seg[h][s]]; return; } int m = (s + e) / 2; buildgcd(h , s , m , 2 * v); buildgcd(h , m , e , 2 * v + 1); g[h][v] = __gcd(g[h][2 * v] , g[h][2 * v + 1]); } ll getGcd(int l , int r , int h , int s = 0 , int e = cmpx.size() , int v = 1) { if(l <= s && e <= r) return g[h][v]; if(r <= s || e <= l) return 0; int m = (s + e) / 2; return __gcd(getGcd(l , r , h , s , m , 2 * v) , getGcd(l , r , h , m , e , 2 * v + 1)); } ll get(int l , int r , int l2 , int r2 , int s = 0 , int e = cmpx.size() , int h = 0) { if(l <= s && e <= r) { y[maxn - 1] = l2; l2 = lower_bound(seg[h] + s , seg[h] + e , maxn - 1 , cmpy) - seg[h]; y[maxn - 1] = r2; r2 = upper_bound(seg[h] + s , seg[h] + e , maxn - 1 , cmpy) - seg[h]; return getGcd(l2 , r2 , h); } if(r <= s || e <= l) return 0; int m = (s + e) / 2; return __gcd(get(l , r , l2 , r2 , s , m , h + 1) , get(l , r , l2 , r2 , m , e , h + 1)); } void rebuild() { cmpx.clear(); for(int i = 0; i < sz; i++) cmpx.pb(x[i]); sort(cmpx.begin() , cmpx.end()); map<int , int> mp; for(int i = 0; i < sz; i++) { int p = lower_bound(cmpx.begin() , cmpx.end() , x[i]) - cmpx.begin(); p += mp[x[i]]; mp[x[i]]++; tmp[p] = i; } build(); for(int i = 0; i < maxb; i++) buildgcd(i); } void init(int R, int C) { R = R , C = C; } void update(int P, int Q, long long K) { x[sz] = P , y[sz] = Q , val[sz] = K; sz++; if(sz % sq == 0) rebuild(); } long long calculate(int l1, int l2, int r1, int r2) { ll res = 0; for(int i = sz / sq * sq; i < sz; i++) if(l1 <= x[i] && x[i] <= r1 && l2 <= y[i] && y[i] <= r2) res = __gcd(res , val[i]); int l = lower_bound(cmpx.begin() , cmpx.end() , l1) - cmpx.begin(); int r = upper_bound(cmpx.begin() , cmpx.end() , r1) - cmpx.begin(); return __gcd(res , get(l , r , l2 , r2)); }

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;
      ^~~
#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...