| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 956449 | abczz | Game (IOI13_game) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "game.h"
#include <iostream>
#include <vector>
#include <numeric>
#define ll long long
using namespace std;
ll gcd(ll a, ll b) {
if (!b) return a;
else if (!a) return b;
else return gcd(b%a, a);
}
struct SegTree{
struct Node{
ll val = 0;
int chl = -1;
int chr = -1;
};
int cnt = 0;
Node st[20000000];
void get(int &id) {
if (id != -1) return;
st[cnt++] = {0, -1, -1};
id = cnt;
}
void updateC(int &id, int idl, int idr, int l, int r, int y, ll w) {
get(id);
if (l == r) {
if (idl == -1 && idr == -1) st[id].val = w;
else st[id].val = gcd((idl != -1 ? st[idl].val : 0), (idr != -1 ? st[idr].val : 0));
return;
}
int mid = (l+r)/2;
if (y <= mid) {
int tmp = st[id].chl;
updateC(tmp, (idl != -1 ? st[idl].chl : -1), (idr != -1 ? st[idr].chl : -1), l, mid, y, w);
st[id].chl = tmp;
}
else {
int tmp = st[id].chr;
updateC(tmp, (idl != -1 ? st[idl].chr : -1), (idr != -1 ? st[idr].chr : -1), mid+1, r, y, w);
st[id].chr = tmp;
}
st[id].val = gcd((st[id].chl != -1 ? st[st[id].chl].val : 0), (st[id].chr != -1 ? st[st[id].chr].val : 0));
}
void updateR(int &id, int l, int r, int x, int y, ll w) {
get(id);
if (id == cnt) {
int tmp = -1;
get(tmp);
}
int tmp = id+1;
if (l == r) {
updateC(tmp, -1, -1, 0, (int)1e9-1, y, w);
st[id].val = st[id+1].val;
return;
}
int mid = (l+r)/2;
if (x <= mid) {
int tmp = st[id].chl;
updateR(tmp, l, mid, x, y, w);
st[id].chl = tmp;
}
else {
int tmp = st[id].chr;
updateR(tmp, mid+1, r, x, y, w);
st[id].chr = tmp;
}
updateC(tmp, (st[id].chl != -1 ? st[id].chl+1 : -1), (st[id].chr != -1 ? st[id].chr+1 : -1), 0, (ll)1e9-1, y, w);
st[id].val = gcd((st[id].chl != -1 ? st[st[id].chl].val : 0), (st[id].chr != -1 ? st[st[id].chr].val : 0));
}
ll queryC(int id, int l, int r, int ql, int qr) {
if (id == -1 || qr < l || r < ql) return 0;
else if (ql <= l && r <= qr) {
return st[id].val;
}
int mid = (l+r)/2;
return gcd(queryC(st[id].chl, l, mid, ql, qr), queryC(st[id].chr, mid+1, r, ql, qr));
}
ll queryR(int id, int l, int r, int ql, int qr, int qx, int qy) {
if (id == -1 || qr < l || r < ql) return 0;
else if (ql <= l && r <= qr) return queryC(id+1, 0, (int)1e9-1, qx, qy);
int mid = (l+r)/2;
return gcd(queryR(st[id].chl, l, mid, ql, qr, qx, qy), queryR(st[id].chr, mid+1, r, ql, qr, qx, qy));
}
}ST;
void init(int R, int C) {
int rt = -1;
ST.get(rt);
}
void update(int P, int Q, long long K) {
int rt = 0;
ST.updateR(rt, 0, (int)1e9-1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
int rt = 0;
return ST.queryR(rt, 0, (int)1e9-1, P, U, Q, V);
}