제출 #98124

#제출 시각아이디문제언어결과실행 시간메모리
98124MiricaMatei게임 (IOI13_game)C++14
63 / 100
12195 ms32732 KiB
#include <bits/stdc++.h> #include "game.h" using namespace std; int N, M; long long gcd2(long long X, long long Y) { long long tmp; while (X != Y && Y != 0) { tmp = X; X = Y; Y = tmp % Y; } return X; } long long coord(int x, int y) { return 1LL * (y - 1) * N + x; } struct Treap { Treap* left; Treap* right; int sz, prio; long long pos, val, gcd; }; Treap* emptyTreap = new Treap {NULL, NULL, 0, 0, 0LL, 0LL, 0LL}; void recompute(Treap* root) { if (root != emptyTreap) { root->sz = root->left->sz + 1 + root->right->sz; root->gcd = gcd2(gcd2(root->left->gcd, root->right->gcd), root->val); } } pair<Treap*, Treap*> split(Treap* root, int pos) { if (root == emptyTreap) return {emptyTreap, emptyTreap}; pair<Treap*, Treap*> ans; if (root->pos <= pos) { ans.first = root; pair<Treap*, Treap*>aux = split(root->right, pos); ans.second = aux.second; ans.first->right = aux.first; } else { ans.second = root; pair<Treap*, Treap*>aux = split(root->left, pos); ans.first = aux.first; ans.second->left = aux.second; } recompute(ans.first); recompute(ans.second); return ans; } Treap* join(Treap* a, Treap* b) { if (a == emptyTreap) return b; if (b == emptyTreap) return a; if (a->prio < b->prio) { a->right = join(a->right, b); recompute(a); return a; } else { b->left = join(a, b->left); recompute(b); return b; } } Treap* TreapUpdate(Treap* root, long long pos, long long val) { pair<Treap*, Treap*>aux1 = split(root, pos - 1); pair<Treap*, Treap*>aux2 = split(aux1.second, pos); Treap* newTreap = new Treap {emptyTreap, emptyTreap, 1, rand(), pos, val, val}; Treap* view = join(join(aux1.first, newTreap), aux2.second); return view; } long long TreapQuery(Treap* root, long long pos1, long long pos2) { pair<Treap*, Treap*>aux1 = split(root, pos1 - 1); pair<Treap*, Treap*>aux2 = split(aux1.second, pos2); long long answer = 0; if (aux2.first != emptyTreap) answer = aux2.first->gcd; root = join(join(aux1.first, aux2.first), aux2.second); return answer; } struct SegTree { Treap* treap; SegTree* left; SegTree* right; }; SegTree* emptyTree = new SegTree {emptyTreap, NULL, NULL}; SegTree* Root; SegTree* SegTreeUpdate(SegTree* root, int l, int r, int P, int Q, long long K) { if (root == emptyTree) root = new SegTree {emptyTreap, emptyTree, emptyTree}; root->treap = TreapUpdate(root->treap, coord(P, Q), K); if (l == r) return root; int mid = (l + r) / 2; if (P <= mid) root->left = SegTreeUpdate(root->left, l, mid, P, Q, K); else root->right = SegTreeUpdate(root->right, mid + 1, r, P, Q, K); return root; } long long SegTreeQuery(SegTree* root, int l, int r, int P, int Q, int U, int V) { if (root == emptyTree) return 0; if (P <= l && r <= U) return TreapQuery(root->treap, coord(P, Q), coord(U, V)); if (U < l) return 0; if (r < P) return 0; int mid = (l + r) / 2; return gcd2(SegTreeQuery(root->left, l, mid, P, Q, U, V), SegTreeQuery(root->right, mid + 1, r, P, Q, U, V)); } void init(int R, int C) { srand(time(NULL)); Root = emptyTree; N = R; M = C; } void update(int P, int Q, long long K) { Root = SegTreeUpdate(Root, 1, N, P + 1, Q + 1, K); } long long calculate(int P, int Q, int U, int V) { return SegTreeQuery(Root, 1, N, P + 1, Q + 1, U + 1, V + 1); } /*int main() { freopen("date.in", "r", stdin); freopen("date.out", "w", stdout); int R, C; scanf("%d%d", &R, &C); init(R, C); int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { int t; scanf("%d", &t); if (t == 1) { int P, Q; long long K; scanf("%d%d", &P, &Q); scanf("%lld", &K); update(P, Q, K); } else { int P, Q, U, V; scanf("%d%d%d%d", &P, &Q, &U, &V); printf("%lld\n", calculate(P, Q, U, V)); } } return 0; } */

컴파일 시 표준 에러 (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...