| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 382856 |
2021-03-28T10:31:35 Z |
rk42745417 |
Game (IOI13_game) |
C++17 |
|
108 ms |
168684 KB |
/*
-------------- | /
| | /
| | /
| * |/ | | ------ *
| | | | / \
| | |\ | | | |\ |
\ | | | \ | | | | \ |
\ | | | \ | | \ / \ |
V | | \ \__/| ----- \ |
*/
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
/*--------------------------------------------------------------------------------------*/
#include "game.h"
const int N = 1e6 + 25;
mt19937 rnd(time(0));
struct segtree {
struct Treap {
struct node {
int l, r, key, pri;
ll v, gd;
node(): l(0), r(0), key(0), pri(0), v(0), gd(0) { }
node(int p): l(0), r(0), key(p), pri(rnd()), v(0), gd(0) { }
} arr[N * 5];
int t = 1;
inline int new_node(int x) {
arr[t] = node(x);
return t++;
}
inline ll gd(int p) { return p ? arr[p].gd : 0; }
inline void pull(int p) { arr[p].gd = __gcd(__gcd(gd(arr[p].l), arr[p].v), gd(arr[p].r)); }
int merge(int a, int b) {
if(!a || !b)
return a ? a : b;
//assert(arr[a].key < arr[b].key);
if(arr[a].pri > arr[b].pri) {
arr[a].r = merge(arr[a].r, b);
pull(a);
return a;
}
else {
arr[b].l = merge(a, arr[b].l);
pull(b);
return b;
}
}
void split(int rt, int &a, int &b, int k) {
if(!rt)
return a = b = 0, void();
if(arr[rt].key < k) {
a = rt;
split(arr[rt].r, arr[a].r, b, k);
pull(a);
}
else {
b = rt;
split(arr[rt].l, a, arr[b].l, k);
pull(b);
}
}
void travesal(int p) {
if(!p)
return;
travesal(arr[p].l);
cout << arr[p].v << ' ';
travesal(arr[p].r);
}
int edt(int rt, int p, ll v) {
int a, b, c;
split(rt, b, c, p + 1);
split(b, a, b, p);
if(!b)
b = new_node(p);
arr[b].v = arr[b].gd = v;
rt = merge(a, b);
rt = merge(rt, c);
return rt;
}
ll que(int rt, int l, int r) { // [l, r)
int a, b, c;
split(rt, b, c, r);
split(b, a, b, l);
pull(b);
ll x = arr[b].gd;
rt = merge(a, b);
rt = merge(rt, c);
return x;
}
} treap;
struct node {
int l, r, v;
node(): l(0), r(0), v(0) { }
} arr[N];
int r, c, t = 1, rt;
void init(int _r, int _c) {
r = _r;
c = _c;
}
int edt(int id, int l, int r, int p, int q, ll v) {
if(p < l || r <= p)
return id;
if(!id)
id = t++;
arr[id].v = treap.edt(arr[id].v, q, v);
if(l == r - 1)
return id;
int m = l + r >> 1;
arr[id].l = edt(arr[id].l, l, m, p, q, v);
arr[id].r = edt(arr[id].r, m, r, p, q, v);
return id;
}
ll que(int id, int l, int r, int ql, int qr, int up, int dw) {
if(r <= ql || qr <= l || !id)
return 0;
if(ql <= l && r <= qr) {
return treap.que(arr[id].v, up, dw);
}
int m = l + r >> 1;
return __gcd(que(arr[id].l, l, m, ql, qr, up, dw), que(arr[id].r, m, r, ql, qr, up, dw));
}
inline void edt(int p, int q, ll v) { rt = edt(rt, 0, r, p, q, v); }
inline ll que(int p, int q, int u, int v) { return que(rt, 0, r, p, u, q, v); }
} tree;
void init(int r, int c) {
tree.init(r, c);
}
void update(int p, int q, long long k) {
tree.edt(p, q, k);
}
long long calculate(int p, int q, int u, int v) {
return tree.que(p, q, u + 1, v + 1);
}
/*
signed main() { EmiliaMyWife
int r, c, q;
cin >> r >> c >> q;
init(r, c);
while(q--) {
int t;
cin >> t;
if(t == 1) {
int p, q; ll k;
cin >> p >> q >> k;
update(p, q, k);
}
else {
int p, q, u, v;
cin >> p >> q >> u >> v;
cout << calculate(p, q, u, v) << '\n';
}
}
}
*/
Compilation message
game.cpp: In member function 'int segtree::edt(int, int, int, int, int, ll)':
game.cpp:121:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
121 | int m = l + r >> 1;
| ~~^~~
game.cpp: In member function 'll segtree::que(int, int, int, int, int, int, int)':
game.cpp:132:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
132 | int m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
168684 KB |
Output is correct |
| 2 |
Incorrect |
99 ms |
168684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
168684 KB |
Output is correct |
| 2 |
Incorrect |
97 ms |
168624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
168632 KB |
Output is correct |
| 2 |
Incorrect |
97 ms |
168684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
168684 KB |
Output is correct |
| 2 |
Incorrect |
108 ms |
168684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
168684 KB |
Output is correct |
| 2 |
Incorrect |
101 ms |
168684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
