# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
400296 |
2021-05-07T19:45:26 Z |
Antekb |
Game (IOI13_game) |
C++14 |
|
6531 ms |
53752 KB |
#include "game.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<30), M=21142005, K=682005;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
struct node{
node* l=nullptr, *r=nullptr;
int rank, key;
ll val, g;
node(int _key, ll _val): key(_key), val(_val), g(_val) {rank=rng();}
void upd(){
g=val;
if(l)g=gcd2(l->g, g);
if(r)g=gcd2(r->g, g);
}
};
node* merge(node* u, node* v){
if(!u)return v;
if(!v)return u;
assert(u->key < v->key);
if((v->rank)>(u->rank)){
v->l=merge(u, v->l);
v->upd();
return v;
}
else{
u->r=merge(u->r, v);
u->upd();
return u;
}
}
#define mp(x, y) make_pair(x, y)
#define st first
#define nd second
typedef pair<node*, node*> pnn;
pnn split(node* v, int l){
if(!v)return mp(nullptr, nullptr);
if(v->key<l){
pnn a=split(v->r, l);
v->r=a.st;
v->upd();
a.st=v;
return a;
}
else{
pnn a=split(v->l, l);
v->l=a.nd;
v->upd();
a.nd=v;
return a;
}
}
void wyp(node* v){
if(!v) return;
wyp(v->l);
cout<<v->rank<<" "<<v->key<<" "<<v->val<<" "<<v->g<<"\n";
wyp(v->r);
}
/*int wsk1=1;
int l1[M], r1[M];
ll val1[M];
void upd(int v){
if(!v)return;
val1[v]=gcd2(val1[l1[v]], val1[r1[v]]);
}
ll quer1d(int v, int L, int R, int l, int r){
if(!v)return 0;
//cout<<L<<" "<<R<<" "<<v->val<<"q\n";
if(l==L && r==R){
return val1[v];
}
int M=(L+R)>>1;
ll ans=0;
if(l<=M)ans=gcd2(ans, quer1d(l1[v], L, M, l, min(M, r)));
if(r>M)ans=gcd2(ans, quer1d(r1[v], M+1, R, max(l, M+1), r));
return ans;
}*/
ll quer1d(node* v, int l, int r){
//wyp(v);
//cout<<l<<" "<<r<<"\n";
pnn a=split(v, l);
pnn b=split(a.nd, r+1);
ll ans=0;
if(b.st){
ans=b.st->g;
assert(b.st->key >=l && b.st -> key <=r);
}
a.nd=merge(b.st, b.nd);
assert(merge(a.st, a.nd)==v);
//cout<<ans<<"\n";
return ans;
}
/*int upd1d(int v, int L, int R, int i, ll val){
if(!v)v=wsk1++;
if(L==R){
//cout<<v->val<<" "<<val<<" "<<i<<"u\n";
val1[v]=val;
return v;
}
//cout<<L<<" "<<R<<" "<<v->val<<"a\n";
int M=(L+R)>>1;
if(i<=M)l1[v]=upd1d(l1[v], L, M, i, val);
else r1[v]=upd1d(r1[v], M+1, R, i, val);
upd(v);
//cout<<L<<" "<<R<<" "<<v->val<<"b\n";
return v;
}*/
node* upd1d(node* v, int i, ll val){
pnn a=split(v, i);
pnn b=split(a.nd, i+1);
if(b.st){
assert(b.st->key == i);
b.st->val=val;
}
else b.st=new node(i, val);
b.st->upd();
a.nd=merge(b.st, b.nd);
return merge(a.st, a.nd);
}
int wsk2=1;
int l2[K], r2[K];
node* nodes[K];
ll quer2d(int v, int L, int R, int l, int r, int x, int y){
if(!v)return 0;
if(l==L && r==R){
return quer1d(nodes[v], x, y);
}
int M=(L+R)>>1;
ll ans=0;
if(l<=M)ans=gcd2(ans, quer2d(l2[v], L, M, l, min(M, r), x, y));
if(r>M)ans=gcd2(ans, quer2d(r2[v], M+1, R, max(l, M+1), r, x, y));
return ans;
}
int upd2d(int v, int L, int R, int i, int j, ll val){
if(!v)v=wsk2++;
if(L==R){
//cout<<L<<" "<<R<<" "<<i<<" "<<j<<"\n";
nodes[v]=upd1d(nodes[v], j, val);
return v;
}
int M=(L+R)>>1;
if(i<=M)l2[v]=upd2d(l2[v], L, M, i, j, val);
else r2[v]=upd2d(r2[v], M+1, R, i, j, val);
//cout<<L<<" "<<R<<" "<<i<<" "<<j<<"\n";
nodes[v]=upd1d(nodes[v], j, gcd2(quer1d(nodes[l2[v]], j, j), quer1d(nodes[r2[v]], j, j)));
return v;
}
int root=0;
void init(int R, int C) {
/* ... */
for(int i=0; i<K; i++)nodes[i]=nullptr;
}
void update(int P, int Q, long long K) {
root=upd2d(root, 0, N-1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return quer2d(root, 0, N-1, P, U, Q, V);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5580 KB |
Output is correct |
2 |
Correct |
9 ms |
5752 KB |
Output is correct |
3 |
Correct |
10 ms |
5708 KB |
Output is correct |
4 |
Correct |
4 ms |
5580 KB |
Output is correct |
5 |
Correct |
4 ms |
5580 KB |
Output is correct |
6 |
Correct |
10 ms |
5708 KB |
Output is correct |
7 |
Correct |
4 ms |
5580 KB |
Output is correct |
8 |
Correct |
4 ms |
5580 KB |
Output is correct |
9 |
Correct |
8 ms |
5708 KB |
Output is correct |
10 |
Correct |
5 ms |
5584 KB |
Output is correct |
11 |
Correct |
5 ms |
5708 KB |
Output is correct |
12 |
Correct |
4 ms |
5580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5624 KB |
Output is correct |
2 |
Correct |
4 ms |
5580 KB |
Output is correct |
3 |
Correct |
4 ms |
5580 KB |
Output is correct |
4 |
Correct |
1830 ms |
23620 KB |
Output is correct |
5 |
Correct |
1139 ms |
23860 KB |
Output is correct |
6 |
Correct |
3054 ms |
20752 KB |
Output is correct |
7 |
Correct |
3193 ms |
20308 KB |
Output is correct |
8 |
Correct |
1815 ms |
14288 KB |
Output is correct |
9 |
Correct |
3275 ms |
20712 KB |
Output is correct |
10 |
Correct |
2859 ms |
20428 KB |
Output is correct |
11 |
Correct |
4 ms |
5580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5580 KB |
Output is correct |
2 |
Correct |
10 ms |
5708 KB |
Output is correct |
3 |
Correct |
9 ms |
5708 KB |
Output is correct |
4 |
Correct |
4 ms |
5580 KB |
Output is correct |
5 |
Correct |
4 ms |
5580 KB |
Output is correct |
6 |
Correct |
9 ms |
5668 KB |
Output is correct |
7 |
Correct |
4 ms |
5580 KB |
Output is correct |
8 |
Correct |
4 ms |
5580 KB |
Output is correct |
9 |
Correct |
8 ms |
5700 KB |
Output is correct |
10 |
Correct |
5 ms |
5580 KB |
Output is correct |
11 |
Correct |
5 ms |
5708 KB |
Output is correct |
12 |
Correct |
1986 ms |
14160 KB |
Output is correct |
13 |
Correct |
4133 ms |
9256 KB |
Output is correct |
14 |
Correct |
797 ms |
6400 KB |
Output is correct |
15 |
Correct |
4323 ms |
10536 KB |
Output is correct |
16 |
Correct |
1504 ms |
12728 KB |
Output is correct |
17 |
Correct |
2661 ms |
10900 KB |
Output is correct |
18 |
Correct |
4840 ms |
12984 KB |
Output is correct |
19 |
Correct |
4239 ms |
13152 KB |
Output is correct |
20 |
Correct |
3805 ms |
12536 KB |
Output is correct |
21 |
Correct |
4 ms |
5580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5580 KB |
Output is correct |
2 |
Correct |
9 ms |
5700 KB |
Output is correct |
3 |
Correct |
10 ms |
5708 KB |
Output is correct |
4 |
Correct |
3 ms |
5580 KB |
Output is correct |
5 |
Correct |
4 ms |
5580 KB |
Output is correct |
6 |
Correct |
9 ms |
5708 KB |
Output is correct |
7 |
Correct |
4 ms |
5580 KB |
Output is correct |
8 |
Correct |
4 ms |
5580 KB |
Output is correct |
9 |
Correct |
8 ms |
5692 KB |
Output is correct |
10 |
Correct |
5 ms |
5708 KB |
Output is correct |
11 |
Correct |
5 ms |
5728 KB |
Output is correct |
12 |
Correct |
1717 ms |
23688 KB |
Output is correct |
13 |
Correct |
1096 ms |
23748 KB |
Output is correct |
14 |
Correct |
2970 ms |
20788 KB |
Output is correct |
15 |
Correct |
3204 ms |
20488 KB |
Output is correct |
16 |
Correct |
1819 ms |
14232 KB |
Output is correct |
17 |
Correct |
3145 ms |
20656 KB |
Output is correct |
18 |
Correct |
2801 ms |
20176 KB |
Output is correct |
19 |
Correct |
1841 ms |
14276 KB |
Output is correct |
20 |
Correct |
4085 ms |
9352 KB |
Output is correct |
21 |
Correct |
745 ms |
6212 KB |
Output is correct |
22 |
Correct |
4312 ms |
10632 KB |
Output is correct |
23 |
Correct |
1542 ms |
12824 KB |
Output is correct |
24 |
Correct |
2635 ms |
10980 KB |
Output is correct |
25 |
Correct |
4721 ms |
13232 KB |
Output is correct |
26 |
Correct |
4149 ms |
13316 KB |
Output is correct |
27 |
Correct |
3658 ms |
12716 KB |
Output is correct |
28 |
Correct |
1248 ms |
28708 KB |
Output is correct |
29 |
Correct |
2192 ms |
34056 KB |
Output is correct |
30 |
Correct |
4265 ms |
26948 KB |
Output is correct |
31 |
Correct |
3832 ms |
23824 KB |
Output is correct |
32 |
Correct |
714 ms |
14784 KB |
Output is correct |
33 |
Correct |
1058 ms |
15104 KB |
Output is correct |
34 |
Correct |
1654 ms |
29072 KB |
Output is correct |
35 |
Correct |
2505 ms |
23428 KB |
Output is correct |
36 |
Correct |
4886 ms |
31004 KB |
Output is correct |
37 |
Correct |
3843 ms |
31088 KB |
Output is correct |
38 |
Correct |
4074 ms |
30524 KB |
Output is correct |
39 |
Correct |
3419 ms |
27516 KB |
Output is correct |
40 |
Correct |
4 ms |
5580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5580 KB |
Output is correct |
2 |
Correct |
9 ms |
5708 KB |
Output is correct |
3 |
Correct |
8 ms |
5688 KB |
Output is correct |
4 |
Correct |
4 ms |
5580 KB |
Output is correct |
5 |
Correct |
5 ms |
5580 KB |
Output is correct |
6 |
Correct |
9 ms |
5708 KB |
Output is correct |
7 |
Correct |
4 ms |
5580 KB |
Output is correct |
8 |
Correct |
5 ms |
5580 KB |
Output is correct |
9 |
Correct |
11 ms |
5712 KB |
Output is correct |
10 |
Correct |
6 ms |
5584 KB |
Output is correct |
11 |
Correct |
5 ms |
5708 KB |
Output is correct |
12 |
Correct |
1747 ms |
23552 KB |
Output is correct |
13 |
Correct |
1157 ms |
23752 KB |
Output is correct |
14 |
Correct |
2997 ms |
20624 KB |
Output is correct |
15 |
Correct |
3232 ms |
20324 KB |
Output is correct |
16 |
Correct |
1797 ms |
14016 KB |
Output is correct |
17 |
Correct |
3145 ms |
20420 KB |
Output is correct |
18 |
Correct |
2776 ms |
20280 KB |
Output is correct |
19 |
Correct |
1821 ms |
14276 KB |
Output is correct |
20 |
Correct |
4089 ms |
9312 KB |
Output is correct |
21 |
Correct |
739 ms |
6248 KB |
Output is correct |
22 |
Correct |
4120 ms |
10552 KB |
Output is correct |
23 |
Correct |
1555 ms |
12612 KB |
Output is correct |
24 |
Correct |
2668 ms |
10960 KB |
Output is correct |
25 |
Correct |
4681 ms |
13188 KB |
Output is correct |
26 |
Correct |
4078 ms |
13132 KB |
Output is correct |
27 |
Correct |
3670 ms |
12608 KB |
Output is correct |
28 |
Correct |
1221 ms |
28668 KB |
Output is correct |
29 |
Correct |
2132 ms |
33668 KB |
Output is correct |
30 |
Correct |
4296 ms |
26952 KB |
Output is correct |
31 |
Correct |
3861 ms |
23820 KB |
Output is correct |
32 |
Correct |
712 ms |
14756 KB |
Output is correct |
33 |
Correct |
1080 ms |
15148 KB |
Output is correct |
34 |
Correct |
1644 ms |
29052 KB |
Output is correct |
35 |
Correct |
2500 ms |
23312 KB |
Output is correct |
36 |
Correct |
4756 ms |
30876 KB |
Output is correct |
37 |
Correct |
3884 ms |
30996 KB |
Output is correct |
38 |
Correct |
4032 ms |
30396 KB |
Output is correct |
39 |
Correct |
1797 ms |
51724 KB |
Output is correct |
40 |
Correct |
3566 ms |
53752 KB |
Output is correct |
41 |
Correct |
6531 ms |
43304 KB |
Output is correct |
42 |
Correct |
6120 ms |
35856 KB |
Output is correct |
43 |
Correct |
2871 ms |
48412 KB |
Output is correct |
44 |
Correct |
1147 ms |
15904 KB |
Output is correct |
45 |
Correct |
3130 ms |
29220 KB |
Output is correct |
46 |
Correct |
6458 ms |
52624 KB |
Output is correct |
47 |
Correct |
6487 ms |
52472 KB |
Output is correct |
48 |
Correct |
6466 ms |
52124 KB |
Output is correct |
49 |
Correct |
3 ms |
5580 KB |
Output is correct |