제출 #365215

#제출 시각아이디문제언어결과실행 시간메모리
365215Berted게임 (IOI13_game)C++17
100 / 100
6386 ms48084 KiB
#include "game.h" #include <iostream> #include <algorithm> #include <vector> #include <array> #define ll long long #define pii pair<int, int> #define ppi pair<pii, ll> #define fst first #define snd second using namespace std; inline ll GCD(ll X, ll Y) { ll tmp; while (X != Y && Y != 0) { tmp = X; X = Y; Y = tmp % Y; } return X; } namespace seg { int r, c; vector<pii> Cx; vector<int> Rx; pii C[10000000]; int keep[10000001]; ll val[10000000]; int SSZ = 0; inline int newNode() { C[SSZ] = {-1, -1}; keep[SSZ] = -2; SSZ++; return SSZ - 1; } inline int newLine() { Cx.push_back({-1, -1}); Rx.push_back(-1); Rx.back() = newNode(); return Cx.size() - 1; } inline void checkChildX(int u, bool b) { if (b && Cx[u].fst == -1) { int rr = newLine(); Cx[u].fst = rr; } if (!b && Cx[u].snd == -1) { int rr = newLine(); Cx[u].snd = rr; } } inline void checkChildY(int u, bool b) { if (b && C[u].fst == -1) { int idx = newNode(); C[u].fst = idx; } if (!b && C[u].snd == -1) { int idx = newNode(); C[u].snd = idx; } } inline int getRoot(int u) { if (u == -1) {return -1;} else {return Rx[u];} } inline int getChild(int u, bool b) { if (u == -1) {return -1;} else if (b) {return C[u].fst;} else {return C[u].snd;} } inline ll getVal(int u) { if (u == -1) {return 0;} return val[u]; } void updateY(int u, int L, int R, int x, ll v) { if (L < R && (keep[u] != -2 && keep[u] != x)) { int M = L + R >> 1; if (keep[u] != -1) { checkChildY(u, keep[u] <= M); if (keep[u] <= M) { val[C[u].fst] = val[u]; keep[C[u].fst] = keep[u]; } else { val[C[u].snd] = val[u]; keep[C[u].snd] = keep[u]; } keep[u] = -1; } checkChildY(u, x <= M); if (x <= M) updateY(C[u].fst, L, M, x, v); else updateY(C[u].snd, M + 1, R, x, v); val[u] = GCD(getVal(C[u].fst), getVal(C[u].snd)); } else {keep[u] = x; val[u] = v;} } ll queryY(int u, int L, int R, int l, int r) { l = max(L, l); r = min(R, r); if (u == -1) {return 0;} if (l <= r) { if (L == l && R == r) {return val[u];} else if (keep[u] != -1) { if (l <= keep[u] && keep[u] <= r) return val[u]; else return 0; } else { int M = L + R >> 1; return GCD(queryY(C[u].fst, L, M, l, r), queryY(C[u].snd, M + 1, R, l, r)); } } return 0; } void updateX(int u, int L, int R, int x, int y, ll v) { if (L < R) { int M = L + R >> 1; checkChildX(u, x <= M); if (x <= M) updateX(Cx[u].fst, L, M, x, y, v); else updateX(Cx[u].snd, M + 1, R, x, y, v); v = GCD(queryY(getRoot(Cx[u].fst), 0, r - 1, y, y), queryY(getRoot(Cx[u].snd), 0, r - 1, y, y)); } updateY(Rx[u], 0, r - 1, y, v); } ll queryX(int u, int L, int R, int lx, int rx, int ly, int ry) { lx = max(lx, L); rx = min(rx, R); if (u == -1) return 0; if (lx <= rx) { if (L == lx && R == rx) {return queryY(Rx[u], 0, r - 1, ly, ry);} else { int M = L + R >> 1; return GCD(queryX(Cx[u].fst, L, M, lx, rx, ly, ry), queryX(Cx[u].snd, M + 1, R, lx, rx, ly, ry)); } } return 0; } } void init(int R, int C) { seg :: r = R; seg :: c = C; seg :: newLine(); } void update(int P, int Q, ll K) { seg :: updateX(0, 0, seg :: c - 1, Q, P, K); } long long calculate(int P, int Q, int U, int V) { return seg :: queryX(0, 0, seg :: c - 1, Q, V, P, U); }

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In function 'void seg::updateY(int, int, int, int, long long int)':
game.cpp:102:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |             int M = L + R >> 1;
      |                     ~~^~~
game.cpp: In function 'long long int seg::queryY(int, int, int, int, int)':
game.cpp:141:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  141 |                 int M = L + R >> 1;
      |                         ~~^~~
game.cpp: In function 'void seg::updateX(int, int, int, int, int, long long int)':
game.cpp:152:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  152 |             int M = L + R >> 1;
      |                     ~~^~~
game.cpp: In function 'long long int seg::queryX(int, int, int, int, int, int, int)':
game.cpp:172:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  172 |                 int M = L + R >> 1;
      |                         ~~^~~
#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...