# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
220385 |
2020-04-07T19:15:04 Z |
YouKnowWho |
Game (IOI13_game) |
C++17 |
|
3289 ms |
73500 KB |
#include<bits/stdc++.h>
#include "game.h"
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e5 + 9;
struct node {
node *l, *r;
int pos, key, mn, mx;
long long val, g;
node(int position, long long value) {
l = r = nullptr;
mn = mx = pos = position;
key = rnd();
val = g = value;
}
void pull() {
g = val;
if(l) g = __gcd(g, l->g);
if(r) g = __gcd(g, r->g);
mn = (l ? l->mn : pos);
mx = (r ? r->mx : pos);
}
};
//memory O(n)
struct treap
{
node *root;
treap() {
root = nullptr;
}
void split(node *t, int pos, node *&l, node *&r)
{
if (t == nullptr) {
l = r = nullptr;
return;
}
if (t->pos < pos) {
split(t->r, pos, l, r);
t->r = l;
l = t;
}
else {
split(t->l, pos, l, r);
t->l = r;
r = t;
}
t->pull();
}
node* merge(node *l, node *r)
{
if (!l || !r) return l ? l : r;
if (l->key < r->key) {
l->r = merge(l->r, r);
l->pull();
return l;
}
r->l = merge(l, r->l);
r->pull();
return r;
}
bool find(int pos)
{
node *t = root;
while (t) {
if (t->pos == pos) return true;
if (t->pos > pos) t = t->l;
else t = t->r;
}
return false;
}
void upd(node *t, int pos, long long val)
{
if (t->pos == pos) {
t->val = val;
t->pull();
return;
}
if (t->pos > pos) upd(t->l, pos, val);
else upd(t->r, pos, val);
t->pull();
}
void insert(int pos, long long val) //set a_pos = val
{
if (find(pos)) upd(root, pos, val);
else {
node *l, *r;
split(root, pos, l, r);
root = merge(merge(l, new node(pos, val)), r);
}
}
long long query(node *t, int st, int en)
{
if (t->mx < st || en < t->mn) return 0;
if (st <= t->mn && t->mx <= en) return t->g;
long long ans = (st <= t->pos && t->pos <= en ? t->val : 0);
if (t->l) ans = __gcd(ans, query(t->l, st, en));
if (t->r) ans = __gcd(ans, query(t->r, st, en));
return ans;
}
long long query(int l, int r) //gcd of a_i such that l <= i <= r
{
if (!root) return 0;
return query(root, l, r);
}
void print(node *t) {
if (!t) return;
print(t->l);
cout << t->val << " ";
print(t->r);
}
};
//total memory along with treap = nlogn
struct ST
{
ST *l, *r;
treap t;
int b, e;
ST()
{
l = r = nullptr;
}
ST(int st, int en)
{
l = r = nullptr;
b = st, e = en;
}
void fix(int pos)
{
long long val = 0;
if (l) val = __gcd(val, l->t.query(pos, pos));
if (r) val = __gcd(val, r->t.query(pos, pos));
t.insert(pos, val);
}
void upd(int x, int y, long long val) //set a[x][y] = val
{
if (e < x || x < b) return;
if (b == e) {
t.insert(y, val);
return;
}
if (b != e) {
if (x <= (b + e) / 2) {
if (!l) l = new ST(b, (b + e) / 2);
l->upd(x, y, val);
}
else {
if (!r) r = new ST((b + e) / 2 + 1, e);
r->upd(x, y, val);
}
}
fix(y);
}
long long query(int i, int j, int st, int en) //gcd of a[x][y] such that i <= x <= j && st <= y <= en
{
if (e < i || j < b) return 0;
if (i <= b && e <= j) return t.query(st, en);
long long ans = 0;
if (l) ans = __gcd(ans, l->query(i, j, st, en));
if (r) ans = __gcd(ans, r->query(i, j, st, en));
return ans;
}
};
int r, c, q;
ST t;
void init(int R, int C) {
r = R; c = C;
t = ST(0, r - 1);
}
void update(int P, int Q, long long K) {
t.upd(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return t.query(P, U, Q, V);
}
//int32_t main()
//{
// int n, m; cin >> n >> m;
// ST t(1, n);
// int q; cin >> q;
// while(q--){
// int ty; cin >> ty;
// if(ty == 1){
// int x, y, v; cin >> x >> y >> v;
// t.upd(x, y, v);
// }
// else{
// int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
// cout << t.query(x1, x2, y1, y2) << '\n';
// }
// }
// return 0;
//}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
256 KB |
Output is correct |
5 |
Correct |
4 ms |
256 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
4 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
4 |
Correct |
622 ms |
11568 KB |
Output is correct |
5 |
Correct |
345 ms |
11384 KB |
Output is correct |
6 |
Correct |
623 ms |
8696 KB |
Output is correct |
7 |
Correct |
670 ms |
8544 KB |
Output is correct |
8 |
Correct |
441 ms |
7672 KB |
Output is correct |
9 |
Correct |
666 ms |
8824 KB |
Output is correct |
10 |
Correct |
633 ms |
8312 KB |
Output is correct |
11 |
Correct |
4 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
256 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
256 KB |
Output is correct |
8 |
Correct |
5 ms |
256 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
512 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
856 ms |
13432 KB |
Output is correct |
13 |
Correct |
1287 ms |
7928 KB |
Output is correct |
14 |
Correct |
278 ms |
5708 KB |
Output is correct |
15 |
Correct |
1402 ms |
9092 KB |
Output is correct |
16 |
Correct |
310 ms |
11540 KB |
Output is correct |
17 |
Correct |
844 ms |
9976 KB |
Output is correct |
18 |
Correct |
1481 ms |
12920 KB |
Output is correct |
19 |
Correct |
1282 ms |
13168 KB |
Output is correct |
20 |
Correct |
1188 ms |
12536 KB |
Output is correct |
21 |
Correct |
5 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
256 KB |
Output is correct |
5 |
Correct |
5 ms |
256 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
256 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
256 KB |
Output is correct |
12 |
Correct |
619 ms |
11676 KB |
Output is correct |
13 |
Correct |
305 ms |
11384 KB |
Output is correct |
14 |
Correct |
627 ms |
8696 KB |
Output is correct |
15 |
Correct |
672 ms |
8568 KB |
Output is correct |
16 |
Correct |
439 ms |
7672 KB |
Output is correct |
17 |
Correct |
686 ms |
8696 KB |
Output is correct |
18 |
Correct |
628 ms |
8440 KB |
Output is correct |
19 |
Correct |
844 ms |
13432 KB |
Output is correct |
20 |
Correct |
1331 ms |
7800 KB |
Output is correct |
21 |
Correct |
295 ms |
5724 KB |
Output is correct |
22 |
Correct |
1380 ms |
9228 KB |
Output is correct |
23 |
Correct |
305 ms |
11512 KB |
Output is correct |
24 |
Correct |
850 ms |
9976 KB |
Output is correct |
25 |
Correct |
1482 ms |
13052 KB |
Output is correct |
26 |
Correct |
1258 ms |
13392 KB |
Output is correct |
27 |
Correct |
1194 ms |
12536 KB |
Output is correct |
28 |
Correct |
562 ms |
39288 KB |
Output is correct |
29 |
Correct |
1482 ms |
41944 KB |
Output is correct |
30 |
Correct |
1698 ms |
30232 KB |
Output is correct |
31 |
Correct |
1511 ms |
24688 KB |
Output is correct |
32 |
Correct |
396 ms |
10360 KB |
Output is correct |
33 |
Correct |
560 ms |
10556 KB |
Output is correct |
34 |
Correct |
421 ms |
35704 KB |
Output is correct |
35 |
Correct |
1140 ms |
25336 KB |
Output is correct |
36 |
Correct |
2306 ms |
40056 KB |
Output is correct |
37 |
Correct |
1863 ms |
39968 KB |
Output is correct |
38 |
Correct |
1833 ms |
39416 KB |
Output is correct |
39 |
Correct |
1497 ms |
33088 KB |
Output is correct |
40 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
256 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
646 ms |
11616 KB |
Output is correct |
13 |
Correct |
358 ms |
11288 KB |
Output is correct |
14 |
Correct |
631 ms |
8824 KB |
Output is correct |
15 |
Correct |
671 ms |
8440 KB |
Output is correct |
16 |
Correct |
442 ms |
7536 KB |
Output is correct |
17 |
Correct |
699 ms |
8696 KB |
Output is correct |
18 |
Correct |
636 ms |
8444 KB |
Output is correct |
19 |
Correct |
873 ms |
13560 KB |
Output is correct |
20 |
Correct |
1277 ms |
8056 KB |
Output is correct |
21 |
Correct |
298 ms |
5880 KB |
Output is correct |
22 |
Correct |
1350 ms |
9172 KB |
Output is correct |
23 |
Correct |
317 ms |
11616 KB |
Output is correct |
24 |
Correct |
871 ms |
9848 KB |
Output is correct |
25 |
Correct |
1496 ms |
13048 KB |
Output is correct |
26 |
Correct |
1265 ms |
13048 KB |
Output is correct |
27 |
Correct |
1198 ms |
12536 KB |
Output is correct |
28 |
Correct |
569 ms |
39372 KB |
Output is correct |
29 |
Correct |
1613 ms |
41884 KB |
Output is correct |
30 |
Correct |
1710 ms |
30044 KB |
Output is correct |
31 |
Correct |
1528 ms |
24756 KB |
Output is correct |
32 |
Correct |
398 ms |
10368 KB |
Output is correct |
33 |
Correct |
548 ms |
10616 KB |
Output is correct |
34 |
Correct |
413 ms |
35576 KB |
Output is correct |
35 |
Correct |
1169 ms |
25464 KB |
Output is correct |
36 |
Correct |
2332 ms |
39756 KB |
Output is correct |
37 |
Correct |
1835 ms |
40008 KB |
Output is correct |
38 |
Correct |
1842 ms |
39584 KB |
Output is correct |
39 |
Correct |
773 ms |
71336 KB |
Output is correct |
40 |
Correct |
2674 ms |
73500 KB |
Output is correct |
41 |
Correct |
2782 ms |
55928 KB |
Output is correct |
42 |
Correct |
2401 ms |
43748 KB |
Output is correct |
43 |
Correct |
892 ms |
68052 KB |
Output is correct |
44 |
Correct |
517 ms |
10748 KB |
Output is correct |
45 |
Correct |
1575 ms |
33276 KB |
Output is correct |
46 |
Correct |
3289 ms |
72444 KB |
Output is correct |
47 |
Correct |
3252 ms |
72396 KB |
Output is correct |
48 |
Correct |
3223 ms |
71860 KB |
Output is correct |
49 |
Correct |
4 ms |
256 KB |
Output is correct |