| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 330067 |
2020-11-23T16:09:47 Z |
rk42745417 |
Game (IOI13_game) |
C++17 |
|
13000 ms |
492 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;
/*-----------------------------------------------------------------------------------------------------*/
struct tree_node {
int l = -1, r = -1;
ll v = 0;
//tree_node(ll _v) { v = _v; }
};
tree_node nodes[2000000];
int segtree_t;
struct segtree {
int n, root = -1;
void init(int c) { n = c; }
void edt(int p, ll v) {
root = edt(0, n, root, p, v);
}
int edt(int l, int r, int id, int p, ll v) {
if(r <= p || p < l)
return id;
if(id == -1) {
id = segtree_t++;
}
if(l == r - 1) {
nodes[id].v = v;
return id;
}
int m = l + r >> 1;
nodes[id].l = edt(l, m, nodes[id].l, p, v);
nodes[id].r = edt(m, r, nodes[id].r, p, v);
nodes[id].v = 0;
if(~nodes[id].l)
nodes[id].v = nodes[nodes[id].l].v;
if(~nodes[id].r)
nodes[id].v = __gcd(nodes[id].v, nodes[nodes[id].r].v);
return id;
}
ll que(int l, int r) {
return que(0, n, root, l, r);
}
ll que(int l, int r, int id, int ql, int qr) {
if(qr <= l || r <= ql || id == -1)
return 0;
if(ql <= l && r <= qr)
return nodes[id].v;
int m = l + r >> 1;
return __gcd(que(l, m, nodes[id].l, ql, qr), que(m, r, nodes[id].r, ql, qr));
}
};
struct two_d_segtree {
int nr, nc, t = 0, root = -1;
struct node {
int l = -1, r = -1;
segtree v;
node(int c) { v.init(c); }
};
vector<node> arr;
void init(int x, int y) { nr = x, nc = y; }
void edt(int x, int y, ll v) {
root = edt(0, nr, x, y, root, v);
}
int edt(int l, int r, int x, int y, int id, ll v) {
if(l > x || r <= x)
return id;
if(id == -1) {
arr.push_back(node(nc));
id = t++;
}
if(l == r - 1) {
arr[id].v.edt(y, v);
//return 1 when in left child
return id;
}
int m = l + r >> 1;
arr[id].l = edt(l, m, x, y, arr[id].l, v);
arr[id].r = edt(m, r, x, y, arr[id].r, v);
arr[id].v.edt(y, __gcd(~arr[id].l ? arr[arr[id].l].v.que(y, y + 1) : 0, ~arr[id].r ? arr[arr[id].r].v.que(y, y + 1) : 0));
return id;
}
ll que(int x1, int y1, int x2, int y2) {
return que(0, nr, root, x1, x2, y1, y2);
}
ll que(int l, int r, int id, int x1, int x2, int y1, int y2) {
if(r <= x1 || x2 <= l || id == -1)
return 0;
if(x1 <= l && r <= x2)
return arr[id].v.que(y1, y2);
int m = l + r >> 1;
return __gcd(que(l, m, arr[id].l, x1, x2, y1, y2), que(m, r, arr[id].r, x1, x2, y1, y2));
}
} tree;
#include "game.h"
void init(int r, int c) {
tree.init(r, c);
}
void update(int x, int y, long long k) {
tree.edt(x, y, k);
}
long long calculate(int a, int b, int c, int d) {
if(a > c)
swap(a, c);
if(b > d)
swap(b, d);
return calculate(a, b, c + 1, d + 1);
}
/*
signed main() { EmiliaMyWife
int r, c, n;
cin >> r >> c >> n;
tree.init(r, c);
while(n--) {
int t;
cin >> t;
if(t == 1) {
int x, y;
ll k;
cin >> x >> y >> k;
tree.edt(x, y, k);
}
else {
int a, b, c, d;
cin >> a >> b >> c >> d;
if(a > c)
swap(a, c);
if(b > d)
swap(b, d);
cout << tree.que(a, b, c + 1, d + 1) << '\n';
}
}
}
*/
Compilation message
game.cpp: In member function 'int segtree::edt(int, int, int, int, ll)':
game.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int m = l + r >> 1;
| ~~^~~
game.cpp: In member function 'll segtree::que(int, int, int, int, int)':
game.cpp:68:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int m = l + r >> 1;
| ~~^~~
game.cpp: In member function 'int two_d_segtree::edt(int, int, int, int, int, ll)':
game.cpp:96:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
96 | int m = l + r >> 1;
| ~~^~~
game.cpp: In member function 'll two_d_segtree::que(int, int, int, int, int, int, int)':
game.cpp:110:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
110 | int m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
13052 ms |
364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
13094 ms |
364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
13068 ms |
364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
13075 ms |
364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
13077 ms |
492 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
