Submission #1081963

#TimeUsernameProblemLanguageResultExecution timeMemory
1081963TheQuantiXGame (IOI13_game)C++17
63 / 100
2688 ms256000 KiB
#include <bits/stdc++.h> #include "game.h" using namespace std; using ll = long long; ll n, m, q, k, x, y, a, b, c; struct segtree1d { vector<ll> tr; vector<ll> pl, pr; segtree1d() { tr.assign(1, 0); pl.assign(1, -1); pr.assign(1, -1); } void extend(ll x) { for (int i = 0; i < 2; i++) { tr.push_back(0); pl.push_back(-1); pr.push_back(-1); } pl[x] = tr.size() - 2; pr[x] = tr.size() - 1; } void update(ll x, ll l, ll r, ll idx, ll val) { // cout << x << ' ' << l << ' ' << r << ' ' << ' ' << idx << ' ' << val << '\n'; if (l == r) { tr[x] = val; return; } if (pl[x] == -1) { extend(x); } ll mid = (r + l) / 2; if (idx <= mid) { update(pl[x], l, mid, idx, val); } else { update(pr[x], mid + 1, r, idx, val); } tr[x] = gcd(tr[pl[x]], tr[pr[x]]); } ll query(ll x, ll l, ll r, ll L, ll R) { if (r < l) { return 0; } if (r < L) { return 0; } if (R < l) { return 0; } if (R < L) { return 0; } if (L <= l && r <= R) { return tr[x]; } if (pl[x] == -1) { extend(x); } ll mid = (r + l) / 2; return gcd(query(pl[x], l, mid, L, R), query(pr[x], mid + 1, r, L, R)); } }; struct segtree { vector<segtree1d> tr; vector<ll> pl, pr; segtree() { tr.assign(1, segtree1d()); pl.assign(1, -1); pr.assign(1, -1); } void extend(ll x) { for (int i = 0; i < 2; i++) { tr.push_back(segtree1d()); pl.push_back(-1); pr.push_back(-1); } pl[x] = tr.size() - 2; pr[x] = tr.size() - 1; } void update(ll x, ll l, ll r, ll X, ll Y, ll val) { // cout << x << ' ' << l << ' ' << r << ' ' << ' ' << X << ' ' << Y << ' ' << val << '\n'; if (l == r) { tr[x].update(0, 0, m, Y, val); return; } if (pl[x] == -1) { extend(x); } ll mid = (r + l) / 2; if (X <= mid) { update(pl[x], l, mid, X, Y, val); } else { update(pr[x], mid + 1, r, X, Y, val); } tr[x].update(0, 0, m, Y, gcd(tr[pl[x]].query(0, 0, m, Y, Y), tr[pr[x]].query(0, 0, m, Y, Y))); } ll query(ll x, ll l, ll r, ll LX, ll RX, ll LY, ll RY) { if (r < l) { return 0; } if (r < LX) { return 0; } if (RX < l) { return 0; } if (RX < LX) { return 0; } if (LX <= l && r <= RX) { return tr[x].query(0, 0, m, LY, RY); } if (pl[x] == -1) { extend(x); } ll mid = (r + l) / 2; return gcd(query(pl[x], l, mid, LX, RX, LY, RY), query(pr[x], mid + 1, r, LX, RX, LY, RY)); } }; segtree sg; void init(int R, int C) { n = R; m = C; sg = segtree(); } void update(int P, int Q, long long K) { sg.update(0, 0, n, P, Q, K); // cout << '\n'; // cout << P << ' ' << Q << ' ' << K << endl; } long long calculate(int P, int Q, int U, int V) { return sg.query(0, 0, n, P, U, Q, V); }
#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...