# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1113707 |
2024-11-17T07:54:12 Z |
Gray |
Game (IOI13_game) |
C++17 |
|
5952 ms |
107592 KB |
#include<bits/stdc++.h>
#include <random>
#include "game.h"
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
mt19937 mt(time(nullptr));
struct Treap{
struct Node{
Node *left, *right;
ll x, y, gcd, fgcd;
Node(ll _x, ll _gcd){
left=right=nullptr;
x=_x; gcd=fgcd=_gcd;
y=mt();
}
Node(ll _x, ll _y, ll _gcd){
left=right=NULL;
x=_x; y=_y; gcd=fgcd=_gcd;
}
};
Node * root;
Treap(){
root=new Node(-1, 2e18, 0);
}
void upd(Node * t){
if (!t) return;
t->fgcd=t->gcd;
if (t->left) t->fgcd=__gcd(t->left->fgcd, t->fgcd);
if (t->right) t->fgcd=__gcd(t->right->fgcd, t->fgcd);
}
void split(Node *par, Node*&wl, Node*&wr, ll x){
if (!par){
wl=wr=nullptr;
}else if (par->x<=x){
split(par->right, par->right, wr, x); wl=par;
}else{
split(par->left, wl, par->left, x); wr=par;
}
upd(wl); upd(wr);
}
void merge(Node *& npar, Node *l, Node *r){
if (!l or !r){
npar=l?l:r;
}else if (l->y>r->y){
merge(l->right, l->right, r); npar=l;
}else{
merge(r->left, l, r->left); npar=r;
}
upd(npar);
}
void insert(Node *& cur, Node * item){
if (!cur){
cur=item;
}else if (cur->y>=item->y){
insert(cur->x<=item->x?cur->right:cur->left, item);
}else{
split(cur, item->left, item->right, item->x); cur=item;
}
upd(cur);
}
ll query_range(Node *& cur, ll l, ll r){
Node * t1, * t2, * t3;
split(cur, t1, t2, l-1);
split(t2, t2, t3, r);
ll res=t2?t2->fgcd:0;
merge(cur, t1, t2);
merge(cur, cur, t3);
return res;
}
void update(Node * cur, ll x, ll newval){
if (!cur){
insert(root, new Node(x, newval));
return;
}else if (cur->x==x){
cur->gcd=newval;
}else if (cur->x<x){
update(cur->right, x, newval);
}else{
update(cur->left, x, newval);
}
upd(cur);
}
void update(ll x, ll newval){
update(root, x, newval);
}
void insert(ll x, ll val){
insert(root, new Node(x, val));
}
ll query(ll l, ll r){
return query_range(root, l, r);
}
};
// struct SegTree1D{
// struct Node{
// ll left, right, val;
// Node(){
// left=right=-1;
// val=0;
// }
// };
// vector<Node> nodes;
// ll add_node(){
// nodes.push_back(Node());
// return nodes.size()-1;
// }
// map<int, ll> leaves;
// int rsz;
// SegTree1D(int N){
// rsz=N;
// add_node();
// }
// void update(ll tl, ll tr, ll v, ll i, ll x){
// if (tl==tr){
// nodes[v].val=x;
// leaves[tl]=v;
// }else{
// ll tm = (tl+tr)/2;
// if (i<=tm){
// if (nodes[v].left==-1) nodes[v].left=add_node();
// update(tl, tm, nodes[v].left, i, x);
// }else{
// if (nodes[v].right==-1) nodes[v].right=add_node();
// update(tm+1, tr, nodes[v].right, i, x);
// }
// nodes[v].val=0;
// if (nodes[v].left!=-1) nodes[v].val=__gcd(nodes[nodes[v].left].val, nodes[v].val);
// if (nodes[v].right!=-1) nodes[v].val=__gcd(nodes[nodes[v].right].val, nodes[v].val);
// }
// }
// void update(ll i, ll x){
// update(0, rsz-1, 0, i, x);
// }
// ll query(ll tl, ll tr, ll v, ll l, ll r){
// if (tl==l and tr==r){
// return nodes[v].val;
// }
// else if (l>r) return 0;
// else{
// ll tm = (tl+tr)/2;
// ll res=0;
// if (nodes[v].left!=-1) res=__gcd(res, query(tl, tm, nodes[v].left, l, min(r, tm)));
// if (nodes[v].right!=-1) res=__gcd(res, query(tm+1, tr, nodes[v].right, max(l, tm+1), r));
// return res;
// }
// }
// ll query(int l, int r){
// return query(0, rsz-1, 0, l, r);
// }
// ll getval(int ind){
// if (!leaves.count(ind)) return 0;
// return nodes[leaves[ind]].val;
// }
// };
struct SegTree2D{
struct mNode{
mNode *left, *right;
Treap *val;
int csz;
mNode(int _csz){
csz=_csz;
left=right=nullptr;
val = new Treap();
}
void update(int tl, int tr, int i, int j, ll x){
if (tl==tr){
// cout << "Entered" << endl;
val->update(j, x);
// cout << "Exited"<< endl;
}else{
int tm = (tl+tr)/2;
if (i<=tm){
if (!left) left=new mNode(csz);
left->update(tl, tm, i, j, x);
}else{
if (!right) right=new mNode(csz);
right->update(tm+1, tr, i, j, x);
}
val->update(j, __gcd((left?left->val->query(j, j):0), (right?right->val->query(j, j):0)));
}
}
ll query(int li, int ri, int lj, int rj, int tl, int tr){
if (tl==li and tr==ri){
// cout << lj << "-" << rj << endl;
ll res= val->query(lj, rj);
// cout << "Success" << endl;
return res;
}else if (li>ri) return 0;
else{
ll ret=0;
int tm = (tl+tr)/2;
if (left and li<=min(ri, tm)) ret=__gcd(ret, left->query(li, min(ri, tm), lj, rj, tl, tm));
if (right and max(li, tm+1)<=ri) ret=__gcd(ret, right->query(max(li, tm+1), ri, lj, rj, tm+1, tr));
return ret;
}
}
};
mNode * root;
ll csz, rsz;
void init(int R, int C){
rsz=R; csz=C;
root = new mNode(csz);
}
void update(int i, int j, ll x){
root->update(0, rsz-1, i, j, x);
}
ll query(int li, int ri, int lj, int rj){
return root->query(li, ri, lj, rj, 0, rsz-1);
}
} DS;
void init(int R, int C) {
DS.init(R, C);
// cout << "Init" << endl;
}
void update(int P, int Q, long long K) {
// cout << "Updating " << P << "-" << Q << "-" << K << endl;
DS.update(P, Q, K);
// cout << "Updated " << P << "-" << Q << "-" << K << endl;
}
long long calculate(int P, int Q, int U, int V) {
/* ... */
ll res= DS.query(P, U, Q, V);
// cout << "Queried" << endl;
return res;
// return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
2 ms |
404 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
2 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
504 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
2 ms |
336 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
508 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
711 ms |
11340 KB |
Output is correct |
5 |
Correct |
295 ms |
11336 KB |
Output is correct |
6 |
Correct |
1244 ms |
8700 KB |
Output is correct |
7 |
Correct |
1415 ms |
8520 KB |
Output is correct |
8 |
Correct |
976 ms |
7540 KB |
Output is correct |
9 |
Correct |
1468 ms |
8508 KB |
Output is correct |
10 |
Correct |
1264 ms |
8264 KB |
Output is correct |
11 |
Correct |
2 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
440 KB |
Output is correct |
3 |
Correct |
2 ms |
508 KB |
Output is correct |
4 |
Correct |
1 ms |
444 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
2 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
504 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
2 ms |
336 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
11 |
Correct |
2 ms |
336 KB |
Output is correct |
12 |
Correct |
1113 ms |
13872 KB |
Output is correct |
13 |
Correct |
2027 ms |
8008 KB |
Output is correct |
14 |
Correct |
312 ms |
5512 KB |
Output is correct |
15 |
Correct |
2139 ms |
9548 KB |
Output is correct |
16 |
Correct |
371 ms |
11848 KB |
Output is correct |
17 |
Correct |
2244 ms |
10056 KB |
Output is correct |
18 |
Correct |
3828 ms |
13212 KB |
Output is correct |
19 |
Correct |
3169 ms |
13452 KB |
Output is correct |
20 |
Correct |
3095 ms |
12872 KB |
Output is correct |
21 |
Correct |
1 ms |
440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
2 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
440 KB |
Output is correct |
6 |
Correct |
2 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
336 KB |
Output is correct |
8 |
Correct |
1 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
336 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
688 ms |
11480 KB |
Output is correct |
13 |
Correct |
309 ms |
11312 KB |
Output is correct |
14 |
Correct |
1300 ms |
8700 KB |
Output is correct |
15 |
Correct |
1428 ms |
8360 KB |
Output is correct |
16 |
Correct |
900 ms |
7600 KB |
Output is correct |
17 |
Correct |
1361 ms |
8456 KB |
Output is correct |
18 |
Correct |
1246 ms |
8192 KB |
Output is correct |
19 |
Correct |
1074 ms |
13640 KB |
Output is correct |
20 |
Correct |
2012 ms |
8008 KB |
Output is correct |
21 |
Correct |
291 ms |
5520 KB |
Output is correct |
22 |
Correct |
2165 ms |
9544 KB |
Output is correct |
23 |
Correct |
348 ms |
11816 KB |
Output is correct |
24 |
Correct |
1995 ms |
10108 KB |
Output is correct |
25 |
Correct |
3609 ms |
13284 KB |
Output is correct |
26 |
Correct |
3099 ms |
13388 KB |
Output is correct |
27 |
Correct |
2813 ms |
12680 KB |
Output is correct |
28 |
Correct |
943 ms |
55704 KB |
Output is correct |
29 |
Correct |
1712 ms |
58440 KB |
Output is correct |
30 |
Correct |
2865 ms |
39056 KB |
Output is correct |
31 |
Correct |
2491 ms |
31708 KB |
Output is correct |
32 |
Correct |
382 ms |
10312 KB |
Output is correct |
33 |
Correct |
699 ms |
10824 KB |
Output is correct |
34 |
Correct |
632 ms |
52044 KB |
Output is correct |
35 |
Correct |
2455 ms |
33932 KB |
Output is correct |
36 |
Correct |
4351 ms |
56428 KB |
Output is correct |
37 |
Correct |
3574 ms |
56456 KB |
Output is correct |
38 |
Correct |
3754 ms |
55844 KB |
Output is correct |
39 |
Correct |
2899 ms |
45896 KB |
Output is correct |
40 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
508 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
2 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
396 KB |
Output is correct |
6 |
Correct |
2 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
336 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
2 ms |
336 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
11 |
Correct |
2 ms |
508 KB |
Output is correct |
12 |
Correct |
673 ms |
11396 KB |
Output is correct |
13 |
Correct |
284 ms |
11252 KB |
Output is correct |
14 |
Correct |
1234 ms |
8672 KB |
Output is correct |
15 |
Correct |
1459 ms |
8520 KB |
Output is correct |
16 |
Correct |
978 ms |
7496 KB |
Output is correct |
17 |
Correct |
1339 ms |
8608 KB |
Output is correct |
18 |
Correct |
1161 ms |
8224 KB |
Output is correct |
19 |
Correct |
1027 ms |
13896 KB |
Output is correct |
20 |
Correct |
1922 ms |
7796 KB |
Output is correct |
21 |
Correct |
288 ms |
5756 KB |
Output is correct |
22 |
Correct |
2091 ms |
9420 KB |
Output is correct |
23 |
Correct |
365 ms |
11848 KB |
Output is correct |
24 |
Correct |
1997 ms |
10100 KB |
Output is correct |
25 |
Correct |
3683 ms |
13200 KB |
Output is correct |
26 |
Correct |
3151 ms |
13384 KB |
Output is correct |
27 |
Correct |
2778 ms |
12764 KB |
Output is correct |
28 |
Correct |
947 ms |
55716 KB |
Output is correct |
29 |
Correct |
1784 ms |
58440 KB |
Output is correct |
30 |
Correct |
2795 ms |
39044 KB |
Output is correct |
31 |
Correct |
2404 ms |
31580 KB |
Output is correct |
32 |
Correct |
378 ms |
10192 KB |
Output is correct |
33 |
Correct |
646 ms |
10712 KB |
Output is correct |
34 |
Correct |
611 ms |
52280 KB |
Output is correct |
35 |
Correct |
2462 ms |
34088 KB |
Output is correct |
36 |
Correct |
4381 ms |
56288 KB |
Output is correct |
37 |
Correct |
3606 ms |
56496 KB |
Output is correct |
38 |
Correct |
3570 ms |
55940 KB |
Output is correct |
39 |
Correct |
1433 ms |
105512 KB |
Output is correct |
40 |
Correct |
2919 ms |
107592 KB |
Output is correct |
41 |
Correct |
4513 ms |
74316 KB |
Output is correct |
42 |
Correct |
3928 ms |
57924 KB |
Output is correct |
43 |
Correct |
1130 ms |
102452 KB |
Output is correct |
44 |
Correct |
687 ms |
10580 KB |
Output is correct |
45 |
Correct |
3121 ms |
45904 KB |
Output is correct |
46 |
Correct |
5649 ms |
106452 KB |
Output is correct |
47 |
Correct |
5952 ms |
106544 KB |
Output is correct |
48 |
Correct |
5563 ms |
106044 KB |
Output is correct |
49 |
Correct |
1 ms |
336 KB |
Output is correct |