oj.uz

답안 #477791

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477791 2021-10-03T17:45:13 Z pypcdev 게임 (IOI13_game) C++17
0 / 100
 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 |     }
      |     ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 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 -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 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 -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 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 -