# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
478519 |
2021-10-07T20:40:07 Z |
KULIKOLD |
Game (IOI13_game) |
C++17 |
|
8426 ms |
110808 KB |
#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> super_set;
int c, rl;
struct Node{
Node* lS;
Node* rS;
ll val;
Node(){
val = 0;
lS = nullptr;
rS = nullptr;
}
};
ll gcd(ll x,ll y){
if(x == 0 or y == 0) return max(x,y);
return __gcd(x,y);
}
ll get_val(Node *v){
if(v == nullptr) return 0;
return v->val;
}
struct NodeST{
Node root;
void del(Node *v){
if (v==nullptr)
return;
del(v->lS);
del(v->rS);
delete v;
}
void del(){
del(root.lS);
del(root.rS);
}
void update(Node* v,int l,int r,int t,ll val){
if (l == r){
(v->val) = val;
return;
}
ll m = (l+r)/2;
if (t <= m){
if (v->lS == nullptr) v->lS = new Node();
update(v->lS,l,m,t,val);
}else{
if (v->rS == nullptr) v->rS = new Node();
update(v->rS,m+1,r,t,val);
}
v->val = gcd(get_val(v->lS),get_val(v->rS));
}
ll get(Node *v,int l,int r,int tl,int tr){
if(v == nullptr or r < tl or tr < l) return 0;
if(tl <= l and r <= tr) {
return v->val;
}
ll m = (l+r)/2;
return gcd(get(v->rS,m+1,r,tl,tr),get(v->lS,l,m,tl,tr));
}
void update(ll t,ll val){
return update(&root,0,c,t,val);
}
ll get(ll tl,ll tr){
return get(&root,0,c,tl,tr);
}
NodeST(){
root = *new Node();
}
};
struct Node2{
Node2 *lS;
Node2 *rS;
NodeST val;
Node2(){
lS = nullptr;
rS = nullptr;
val = *new NodeST();
}
};
void del(Node2 *v){
if (v==nullptr)
return;
del(v->lS);
del(v->rS);
(v->val).del();
delete v;
}
void update(Node2* v,int l,int r,int x,int y,ll val){
if (l == r){
(v->val).update(y,val);
return;
}
ll m = (l+r)/2;
if (x <= m){
if (v->lS == nullptr) v->lS = new Node2();
update(v->lS,l,m,x,y,val);
}else{
if (v->rS == nullptr) v->rS = new Node2();
update(v->rS,m+1,r,x,y,val);
}
ll new_val = 0;
if(v->lS) new_val=gcd(new_val,(v->lS)->val.get(y,y));
if(v->rS) new_val=gcd(new_val,(v->rS)->val.get(y,y));
v->val.update(y,new_val);
}
ll get(Node2 *v,int l,int r,int xl,int xr,int yl,int yr){
if(v == nullptr or r < xl or xr < l) return 0;
if(xl <= l and r <= xr) {
return (v->val).get(yl,yr);
}
ll m = (l+r)/2;
return gcd(get(v->lS,l,m,xl,xr,yl,yr),get(v->rS,m+1,r,xl,xr,yl,yr));
}
Node2 root;
const int SQRT = 3000;
map<pair<int,int>,ll> buf,all;
super_set X,Y;
void updates(int x,int y,ll val){
if (all.count({x,y})){
update(&root,0,rl,X.order_of_key(x),Y.order_of_key(y),val);
all[{x,y}] = val;
return;
}
buf[{x,y}] = val;
if (buf.size()>SQRT){
del(root.lS);
del(root.rS);
root.lS = nullptr;
root.rS = nullptr;
for(auto [cord,val]:buf){
X.insert(cord.first);
Y.insert(cord.second);
all[cord] = val;
}
buf.clear();
rl = X.size();
c = Y.size();
for(auto [cord,val]:all){
update(&root,0,rl,X.order_of_key(cord.first),Y.order_of_key(cord.second),val);
}
}
}
ll get(int xl,int xr,int yl,int yr){
ll ret = 0;
for(auto [cord,val]:buf){
if (xl<=cord.first && cord.first<=xr && yl<=cord.second && cord.second<=yr)
ret = __gcd(ret,val);
}
return __gcd(ret,get(&root,0,rl,X.order_of_key(xl),X.order_of_key(xr+1)-1,Y.order_of_key(yl),Y.order_of_key(yr+1)-1));
}
/*
int main() {
int R,C,n;
cin >> R >> C >> n;
rl = -1;
c = -1;
for (int i = 0; i < n; ++i) {
int type = 0;
cin >> type;
if(type == 1){
int x,y,t;
cin >> x >> y >> t;
updates(x,y,t);
}
else{
int x1,x2,y1,y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << get(x1,x2,y1,y2) << "\n";
}
}
return 0;
}
*/
void init(int R,int C){
rl = -1;
c = -1;
root = *new Node2();
}
void update(int P,int Q,ll K){
updates(P,Q,K);
}
ll calculate(int P,int Q,int U,int V){
return get(P,U,Q,V);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
4855 ms |
9420 KB |
Output is correct |
5 |
Correct |
4602 ms |
9640 KB |
Output is correct |
6 |
Correct |
4774 ms |
6800 KB |
Output is correct |
7 |
Correct |
3106 ms |
6560 KB |
Output is correct |
8 |
Correct |
3597 ms |
3712 KB |
Output is correct |
9 |
Correct |
3746 ms |
6392 KB |
Output is correct |
10 |
Correct |
3210 ms |
5908 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
5309 ms |
16280 KB |
Output is correct |
13 |
Correct |
3774 ms |
6468 KB |
Output is correct |
14 |
Correct |
950 ms |
988 KB |
Output is correct |
15 |
Correct |
4399 ms |
8440 KB |
Output is correct |
16 |
Correct |
5538 ms |
18752 KB |
Output is correct |
17 |
Correct |
4207 ms |
8468 KB |
Output is correct |
18 |
Correct |
4918 ms |
19040 KB |
Output is correct |
19 |
Correct |
5291 ms |
19136 KB |
Output is correct |
20 |
Correct |
5301 ms |
18700 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
4635 ms |
9376 KB |
Output is correct |
13 |
Correct |
4329 ms |
9752 KB |
Output is correct |
14 |
Correct |
4449 ms |
6644 KB |
Output is correct |
15 |
Correct |
3037 ms |
6232 KB |
Output is correct |
16 |
Correct |
3493 ms |
3756 KB |
Output is correct |
17 |
Correct |
3629 ms |
6312 KB |
Output is correct |
18 |
Correct |
3145 ms |
6124 KB |
Output is correct |
19 |
Correct |
5142 ms |
16340 KB |
Output is correct |
20 |
Correct |
3692 ms |
6468 KB |
Output is correct |
21 |
Correct |
945 ms |
720 KB |
Output is correct |
22 |
Correct |
4395 ms |
8420 KB |
Output is correct |
23 |
Correct |
5373 ms |
18820 KB |
Output is correct |
24 |
Correct |
4082 ms |
8480 KB |
Output is correct |
25 |
Correct |
4864 ms |
19012 KB |
Output is correct |
26 |
Correct |
5435 ms |
19436 KB |
Output is correct |
27 |
Correct |
5309 ms |
18760 KB |
Output is correct |
28 |
Correct |
3481 ms |
20420 KB |
Output is correct |
29 |
Correct |
5562 ms |
40868 KB |
Output is correct |
30 |
Correct |
7133 ms |
18556 KB |
Output is correct |
31 |
Correct |
4966 ms |
12012 KB |
Output is correct |
32 |
Correct |
934 ms |
800 KB |
Output is correct |
33 |
Correct |
1987 ms |
964 KB |
Output is correct |
34 |
Correct |
5722 ms |
37832 KB |
Output is correct |
35 |
Correct |
4332 ms |
11412 KB |
Output is correct |
36 |
Correct |
5467 ms |
38212 KB |
Output is correct |
37 |
Correct |
5642 ms |
38340 KB |
Output is correct |
38 |
Correct |
5645 ms |
37692 KB |
Output is correct |
39 |
Correct |
5156 ms |
24088 KB |
Output is correct |
40 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
4648 ms |
9584 KB |
Output is correct |
13 |
Correct |
4411 ms |
9692 KB |
Output is correct |
14 |
Correct |
4401 ms |
6472 KB |
Output is correct |
15 |
Correct |
3059 ms |
6384 KB |
Output is correct |
16 |
Correct |
3432 ms |
3852 KB |
Output is correct |
17 |
Correct |
3569 ms |
6476 KB |
Output is correct |
18 |
Correct |
3081 ms |
6240 KB |
Output is correct |
19 |
Correct |
5191 ms |
16488 KB |
Output is correct |
20 |
Correct |
3672 ms |
6708 KB |
Output is correct |
21 |
Correct |
902 ms |
808 KB |
Output is correct |
22 |
Correct |
4333 ms |
8608 KB |
Output is correct |
23 |
Correct |
5499 ms |
18888 KB |
Output is correct |
24 |
Correct |
4050 ms |
8784 KB |
Output is correct |
25 |
Correct |
4827 ms |
19212 KB |
Output is correct |
26 |
Correct |
5223 ms |
19488 KB |
Output is correct |
27 |
Correct |
5212 ms |
18736 KB |
Output is correct |
28 |
Correct |
3394 ms |
20552 KB |
Output is correct |
29 |
Correct |
5629 ms |
40720 KB |
Output is correct |
30 |
Correct |
7237 ms |
18492 KB |
Output is correct |
31 |
Correct |
5117 ms |
11972 KB |
Output is correct |
32 |
Correct |
913 ms |
836 KB |
Output is correct |
33 |
Correct |
2019 ms |
1072 KB |
Output is correct |
34 |
Correct |
5773 ms |
37828 KB |
Output is correct |
35 |
Correct |
4238 ms |
11428 KB |
Output is correct |
36 |
Correct |
5560 ms |
38088 KB |
Output is correct |
37 |
Correct |
5597 ms |
38128 KB |
Output is correct |
38 |
Correct |
5678 ms |
37744 KB |
Output is correct |
39 |
Correct |
4344 ms |
58616 KB |
Output is correct |
40 |
Correct |
7871 ms |
110808 KB |
Output is correct |
41 |
Correct |
8426 ms |
49672 KB |
Output is correct |
42 |
Correct |
7768 ms |
32172 KB |
Output is correct |
43 |
Correct |
7044 ms |
108612 KB |
Output is correct |
44 |
Correct |
2676 ms |
836 KB |
Output is correct |
45 |
Correct |
5030 ms |
24116 KB |
Output is correct |
46 |
Correct |
8116 ms |
109024 KB |
Output is correct |
47 |
Correct |
8137 ms |
109296 KB |
Output is correct |
48 |
Correct |
8163 ms |
108796 KB |
Output is correct |
49 |
Correct |
1 ms |
204 KB |
Output is correct |