제출 #1121459

#제출 시각아이디문제언어결과실행 시간메모리
1121459joelgun14게임 (IOI13_game)C++17
80 / 100
3058 ms256000 KiB
#include <bits/stdc++.h> #include "game.h" #pragma GCC optimize("O2") #define ll long long #define mp make_pair #define ins insert #define lb lower_bound #define pb push_back #define ub upper_bound #define fi first #define se second using namespace std; const int lim = 1e9 + 5; 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; } struct nodex { int l = -1, r = -1, nx = -1; }; struct nodey { int l = -1, r = -1; ll val = 0; }; const int lim2 = 1.5e7; int lx[660000], rx[666000], nx[660000]; int ly[lim2], ry[lim2]; ll v[lim2]; struct segtree { int xsize = 1, ysize = 0; segtree() { memset(lx, -1, sizeof(lx)); memset(rx, -1, sizeof(rx)); memset(nx, -1, sizeof(nx)); memset(ly, -1, sizeof(ly)); memset(ry, -1, sizeof(ry)); memset(v, 0, sizeof(v)); } int add_nodex() { return ++xsize; } int add_nodey() { return ++ysize; } void update_node(int nd) { v[nd] = 0; if(ly[nd] != -1) v[nd] = gcd2(v[ly[nd]], v[nd]); if(ry[nd] != -1) v[nd] = gcd2(v[ry[nd]], v[nd]); } void update_x(int x, int y, ll val) { int nd = 0, cl = 0, cr = lim - 1; vector<int> nodes = {}; while(cl < cr) { int mid = (cl + cr) >> 1; if(x <= mid) { cr = mid; if(lx[nd] == -1) lx[nd] = add_nodex(); nd = lx[nd]; } else { cl = mid + 1; if(rx[nd] == -1) rx[nd] = add_nodex(); nd = rx[nd]; } nodes.pb(nd); } reverse(nodes.begin(), nodes.end()); // from smallest to largest for(auto x : nodes) { if(nx[x] == -1) nx[x] = add_nodey(); update_y(nx[x], x, y, val); } } void update_y(int nd, int ndx, int y, ll val) { int cl = 0, cr = lim - 1; vector<int> nodes = {nd}; while(cl < cr) { int mid = (cl + cr) >> 1; if(y <= mid) { cr = mid; if(ly[nd] == -1) ly[nd] = add_nodey(); nd = ly[nd]; } else { cl = mid + 1; if(ry[nd] == -1) ry[nd] = add_nodey(); nd = ry[nd]; } nodes.pb(nd); } nodes.pop_back(); reverse(nodes.begin(), nodes.end()); if(lx[ndx] == -1 && rx[ndx] == -1) v[nd] = val; else { // take from v[ndx].l and v[ndx].r v[nd] = gcd2(lx[ndx] != -1 ? query_y(nx[lx[ndx]], 0, lim - 1, y, y) : 0, rx[ndx] != -1 ? query_y(nx[rx[ndx]], 0, lim - 1, y, y) : 0); } for(auto x : nodes) { // cerr << "UPDATE " << x << endl; update_node(x); } } ll query_x(int nd, int cl, int cr, int l, int r, int y1, int y2) { if(nd == -1 || cl > r || cr < l) return 0; else if(cl >= l && cr <= r) { // cerr << "GET Y " << cl << " " << cr << endl; // cerr << l << " " << r << " " << y1 << " " << y2 << endl; return query_y(nx[nd], 0, lim - 1, y1, y2); } else { int mid = (cl + cr) >> 1; return gcd2(query_x(lx[nd], cl, mid, l, r, y1, y2), query_x(rx[nd], mid + 1, cr, l, r, y1, y2)); } } ll query_y(int nd, int cl, int cr, int l, int r) { if(nd == -1 || cl > r || cr < l) return 0; else if(cl >= l && cr <= r) { // cerr << "GOT Y " << nd << " " << cl << " " << cr << " " << v[nd].val << endl; return v[nd]; } else { int mid = (cl + cr) >> 1; return gcd2(query_y(ly[nd], cl, mid, l, r), query_y(ry[nd], mid + 1, cr, l, r)); } } }; segtree seg; void init(int R, int C) { } void update(int P, int Q, long long K) { seg.update_x(P, Q, K); } long long calculate(int P, int Q, int U, int V) { // cerr << "QUERY " << endl; return seg.query_x(0, 0, lim - 1, 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...