Submission #122404

#TimeUsernameProblemLanguageResultExecution timeMemory
122404ekremGame (IOI13_game)C++98
80 / 100
5465 ms256000 KiB
#include <bits/stdc++.h> #include "game.h" #define st first #define nd second #define mp make_pair #define pb push_back #define orta ((bas+son)/2) #define mod 1000000007 #define MAXN 20000005 using namespace std; // #define fail(s, x...) do { \ // fprintf(stderr, s "\n", ## x); \ // exit(1); \ // } while(0) typedef long long ll; int n, m, son1, son, sol[MAXN], sag[MAXN], seg[MAXN], sl[MAXN], sg[MAXN]; ll val[MAXN]; ll gcd2(ll X, ll Y) { if(X == 0 || Y == 0) { return X + Y; } ll tmp; while (X != Y && Y != 0) { tmp = X; X = Y; Y = tmp % Y; } return X; } int ver(int k){ if(!k)return 0; return (!seg[k])?seg[k] = ++son:seg[k]; } int slver(int k){ return (!sl[k])?sl[k] = ++son:sl[k]; } int sgver(int k){ return (!sg[k])?sg[k] = ++son:sg[k]; } int solver(int k){ return (!sol[k])?sol[k] = ++son1:sol[k]; } int sagver(int k){ return (!sag[k])?sag[k] = ++son1:sag[k]; } ll qu2(int k, int bas, int son, int x, int y){ if(!k or bas > y or son < x) return 0; if(bas >= x and son <= y) return val[k]; return gcd2(qu2(sl[k], bas, orta, x, y), qu2(sg[k], orta + 1, son, x, y)); } ll qu1(int k, int bas, int son, int x, int y, int xx, int yy){ if(!k or bas > y or son < x) return 0; if(bas >= x and son <= y) return qu2(seg[k], 1, m, xx, yy); return gcd2(qu1(sol[k], bas, orta, x, y, xx, yy), qu1(sag[k], orta + 1, son, x, y, xx, yy)); } void up2(int k, int bas, int son, int x, ll z){ if(bas == son){ val[k] = z; return; } if(x <= orta){ if(!sl[k]){ int kk = slver(k); int bbas = bas, sson = orta; while(bbas < sson){ val[kk] = z; if(x <= ((bbas+sson)/2)) kk = slver(kk), sson = ((bbas+sson)/2); else kk = sgver(kk), bbas = ((bbas+sson)/2) + 1; } val[kk] = z; } else up2(slver(k), bas, orta, x, z); } else{ if(!sg[k]){ int kk = sgver(k); int bbas = orta + 1, sson = son; while(bbas < sson){ val[kk] = z; if(x <= ((bbas+sson)/2)) kk = slver(kk), sson = ((bbas+sson)/2); else kk = sgver(kk), bbas = ((bbas+sson)/2) + 1; } val[kk] = z; } else up2(sgver(k), orta + 1, son, x, z); } val[k] = gcd2(val[sl[k]], val[sg[k]]); } void up1(int k, int bas, int son, int x, int y, ll z){ if(bas == son){ up2(ver(k), 1, m, y, z); return; } if(x <= orta) up1(solver(k), bas, orta, x, y, z); else up1(sagver(k), orta + 1, son, x, y, z); z = gcd2(qu2(ver(sol[k]), 1, m, y, y), qu2(ver(sag[k]), 1, m, y, y)); up2(ver(k), 1, m, y, z); } void init(int R, int C) { n = R;m = C; son1++; } void update(int p, int q, ll k) { up1(1, 1, n, p + 1, q + 1, k); } ll calculate(int p, int q, int u, int v) { return qu1(1, 1, n, p+1, u+1, q+1, v+1); } // int main() { // int R, C, N; // int P, Q, U, V; // long long K; // int i, type; // int res; // FILE *f = fopen("in.txt", "r"); // if (!f) // fail("Failed to open input file."); // res = fscanf(f, "%d", &R); // res = fscanf(f, "%d", &C); // res = fscanf(f, "%d", &N); // init(R, C); // for (i = 0; i < N; i++) { // res = fscanf(f, "%d", &type); // if (type == 1) { // res = fscanf(f, "%d%d%lld", &P, &Q, &K); // update(P, Q, K); // } else if (type == 2) { // res = fscanf(f, "%d%d%d%d", &P, &Q, &U, &V); // printf("%lld\n", calculate(P, Q, U, V)); // } else // fail("Invalid action type in input file."); // } // fclose(f); // return 0; // }

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;
      ^~~
game.cpp:11:1: warning: multi-line comment [-Wcomment]
 // #define fail(s, x...) do { \
 ^
#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...