| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 477790 |
2021-10-03T17:40:24 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();
}
void try_clear(gcdNode*&root){
if(root!=NULL&&root->val==0&&root->left==NULL&&root->right==NULL)delete root;
}
};
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){
v->try_create(v->left);
res=get(v->left,l,m,y1,y2);
}else if(y1>m){
v->try_create(v->right);
res=get(v->right,m+1,r,y1,y2);
}else{
v->try_create(v->left);
v->try_create(v->right);
res=merge(get(v->left,l,m,y1,m),get(v->right,m+1,r,m+1,y2));
}
v->try_clear(v->left);
v->try_clear(v->right);
return res;
}
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;
v->try_create(v->left);
v->try_create(v->right);
if(pos<=m){
upd(v->left,l,m,pos,val);
}else{
upd(v->right,m+1,r,pos,val);
}
v->val=merge(v->left->val,v->right->val);
v->try_clear(v->left);
v->try_clear(v->right);
}
};
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
*/
| # |
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 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 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 |
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 |
- |
