| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 477791 |
2021-10-03T17:45:13 Z |
pypcdev |
Game (IOI13_game) |
C++17 |
|
1 ms |
332 KB |
#include<bits/stdc++.h>
#include"game.h"
using namespace std;
int MAX=1e9;
struct gcdNode{
gcdNode*left;gcdNode*right;
long long val;
gcdNode(){
val=0;
left=NULL;
right=NULL;
}
void try_create(gcdNode*&root){
if(root==NULL)root=new gcdNode();
}
};
long long gcd(long long left,long long right){
if(left==0&&right==0)return 0;
if(left==0||right==0)return left^right;
return __gcd(left,right);
}
long long merge(long long left,long long right){
return gcd(left,right);
//return left+right;
}
struct segTreeNode{
gcdNode*root;
segTreeNode*left;segTreeNode*right;
segTreeNode(){
root=new gcdNode();
left=NULL;
right=NULL;
}
void try_create(segTreeNode*&v){
if(v==NULL)v=new segTreeNode();
}
long long get(gcdNode*&v,int l,int r,int y1,int y2){
if(y1==l&&y2==r){
return v->val;
}
int m=(l+r)/2;
long long res;
if(y2<=m){
if(v->left==NULL)return 0;
return get(v->left,l,m,y1,y2);
}else if(y1>m){
if(v->right==NULL)
return get(v->right,m+1,r,y1,y2);
}else{
long long r1,r2;
if(v->left==NULL)r1=0;
else r1=get(v->left,l,m,y1,m);
if(v->right==NULL)r2=0;
else r2=get(v->right,m+1,r,m+1,y2);
return merge(r1,r2);
}
}
void upd(gcdNode*&v,int l,int r,int pos,long long val){
if(l==pos&&r==pos){
v->val=val;
return;
}
int m=(l+r)/2;
if(pos<=m){
v->try_create(v->left);
upd(v->left,l,m,pos,val);
}else{
v->try_create(v->right);
upd(v->right,m+1,r,pos,val);
}
long long r1,r2;
if(v->left==NULL)r1=0;
else r1=v->left->val;
if(v->right==NULL)r2=0;
else r2=v->right->val;
v->val=merge(r1,r2);
}
};
struct segTreeNode2{
segTreeNode*root;
segTreeNode2(){
root=new segTreeNode();
}
long long get(segTreeNode*&v,int l,int r,int x1,int x2,int y1,int y2){
if(l==x1&&r==x2){
return v->get(v->root,0,MAX,y1,y2);
}
int m=(l+r)/2;
if(x2<=m){
v->try_create(v->left);
return get(v->left,l,m,x1,x2,y1,y2);
}else if(x1>m){
v->try_create(v->right);
return get(v->right,m+1,r,x1,x2,y1,y2);
}else{
v->try_create(v->left);
v->try_create(v->right);
return merge(get(v->left,l,m,x1,m,y1,y2),get(v->right,m+1,r,m+1,x2,y1,y2));
}
}
void upd(segTreeNode*&v,int l,int r,int x,int y,long long val){
if(l==r&&l==x){
v->upd(v->root,0,MAX,y,val);
return;
}
int m=(l+r)/2;
v->try_create(v->left);
v->try_create(v->right);
if(x<=m){
upd(v->left,l,m,x,y,val);
}else{
upd(v->right,m+1,r,x,y,val);
}
//delete &l;
//delete &r;
//delete &x;
//delete &val;
long long res=merge(v->left->get(v->left->root,0,MAX,y,y),v->right->get(v->right->root,0,MAX,y,y));
v->upd(v->root,0,MAX,y,res);
}
};
segTreeNode2 root;
void init(int R,int C){
MAX=max(R,C);
}
void update(int P,int Q,long long K){
root.upd(root.root,0,MAX,Q,P,K);
}
long long calculate(int P,int Q,int U,int V){
return root.get(root.root,0,MAX,Q,V,P,U);
}
/*signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int a,b,c;
cin>>a>>b>>c;
while(c--){
int t;
cin>>t;
if(t==2){
int P,Q,U,V;
cin>>P>>Q>>U>>V;
cout<<"RES: "<<calculate(P,Q,U,V)<<"\n";
}else{
int P,Q;long long val;
cin>>P>>Q>>val;
update(P,Q,val);
}
}
}*/
/*
2 3 9
1 0 0 20
1 0 2 15
1 1 1 12
2 0 0 0 2
2 0 0 1 1
1 0 1 6
1 1 1 14
2 0 0 0 2
2 0 0 1 1
*/
Compilation message
game.cpp: In member function 'long long int segTreeNode::get(gcdNode*&, int, int, int, int)':
game.cpp:42:19: warning: unused variable 'res' [-Wunused-variable]
42 | long long res;
| ^~~
game.cpp:57:5: warning: control reaches end of non-void function [-Wreturn-type]
57 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
