Submission #395867

#TimeUsernameProblemLanguageResultExecution timeMemory
395867pure_memGame (IOI13_game)C++14
63 / 100
1618 ms256004 KiB
#include "game.h" #include <iostream> #include <algorithm> #define ll long long #define X first #define Y second #define MP make_pair using namespace std; ll gcd(ll x, ll y) { if(x < y) swap(x, y); while(y){ x %= y; swap(x, y); } return x; } int n, m, dl, dr; struct node{ node* p[2] = {nullptr, nullptr}; node* p1[2] = {nullptr, nullptr}; ll val = 0; node* getp(int v){ if(!p[v]) p[v] = new node; return p[v]; } node* getp1(int v){ if(!p1[v]) p1[v] = new node; return p1[v]; } void merge(int tl, int tr, node* L, node* R, int pos){ if(!L && !R) return; if(tl == tr){ val = 0; if(L) val = gcd(L->val, val); if(R) val = gcd(R->val, val); return; } int tm = (tl + tr) / 2; if(pos <= tm){ if(L) L = L->p1[0]; if(R) R = R->p1[0]; getp1(0)->merge(tl, tm, L, R, pos); } else{ if(L) L = L->p1[1]; if(R) R = R->p1[1]; getp1(1)->merge(tm + 1, tr, L, R, pos); } val = 0; if(p1[0]) val = gcd(p1[0]->val, val); if(p1[1]) val = gcd(p1[1]->val, val); //cerr << tl << " " << tr << " " << val << " " << this << "s\n"; } void upd1(int tl, int tr, int pos, ll _val){ if(tl == tr) return void(val = _val); int tm = (tl + tr) / 2; //cerr << tl << " s " << tr << "\n"; if(pos <= tm) getp1(0)->upd1(tl, tm, pos, _val); else getp1(1)->upd1(tm + 1, tr, pos, _val); val = 0; if(p1[0]) val = gcd(p1[0]->val, val); if(p1[1]) val = gcd(p1[1]->val, val); } ll get1(int tl, int tr, int l, int r){ if(tl > r || l > tr) return 0; if(tl >= l && tr <= r) return val; int tm = (tl + tr) / 2; ll left = (p1[0] ? p1[0]->get1(tl, tm, l, r): 0); ll right = (p1[1] ? p1[1]->get1(tm + 1, tr, l, r): 0); return gcd(left, right); } void upd(int tl, int tr, int pos, ll _val){ //cerr << tl << " " << tr << " b " << this << "\n"; if(tl == tr){ return void(upd1(1, m, dl, _val)); } int tm = (tl + tr) / 2; if(pos <= tm) getp(0)->upd(tl, tm, pos, _val); else getp(1)->upd(tm + 1, tr, pos, _val); merge(1, m, p[0], p[1], dl); } ll get(int tl, int tr, int l, int r){ if(tl > r || l > tr) return 0; if(tl >= l && tr <= r) return get1(1, m, dl, dr); int tm = (tl + tr) / 2; ll left = (p[0] ? p[0]->get(tl, tm, l, r): 0); ll right = (p[1] ? p[1]->get(tm + 1, tr, l, r): 0); //cerr << tl << " " << tr << " " << left << " z " << right << "\n"; return gcd(left, right); } }root; void init(int R, int C) { n = R, m = C; } void update(int P, int Q, ll K) { // cerr << "was1\n"; dl = Q + 1; //cerr << P + 1 << " " << Q + 1 << "\n"; root.upd(1, n, P + 1, K); // cerr << "was\n"; } long long calculate(int P, int Q, int U, int V) { /* ... */ //cerr << "were\n"; dl = Q + 1, dr = V + 1; //cerr << P + 1 << " " << U + 1 << " " << dl << " " << dr << "\n"; ll tmp = root.get(1, n, P + 1, U + 1); // cerr << tmp << "\n"; return tmp; }
#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...