oj.uz

Submission #477759

# Submission time Handle Problem Language Result Execution time Memory
477759 2021-10-03T11:45:30 Z pypcdev Game (IOI13_game) C++17
63 / 100
 2554 ms 256004 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;
        if(y2<=m){
            v->try_create(v->left);
            return get(v->left,l,m,y1,y2);
        }else if(y1>m){
            v->try_create(v->right);
            return get(v->right,m+1,r,y1,y2);
        }else{
            v->try_create(v->left);
            v->try_create(v->right);
            return merge(get(v->left,l,m,y1,m),get(v->right,m+1,r,m+1,y2));
        }
    }
    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);
    }
};
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);
        }
        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
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 544 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# 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 1 ms 204 KB Output is correct
4 Correct 1175 ms 86116 KB Output is correct
5 Correct 849 ms 75236 KB Output is correct
6 Correct 1624 ms 171972 KB Output is correct
7 Correct 1874 ms 171796 KB Output is correct
8 Correct 1492 ms 168904 KB Output is correct
9 Correct 1695 ms 175880 KB Output is correct
10 Correct 1647 ms 171568 KB Output is correct
11 Correct 0 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 927 ms 28100 KB Output is correct
13 Correct 1365 ms 10692 KB Output is correct
14 Correct 632 ms 2052 KB Output is correct
15 Correct 1717 ms 16708 KB Output is correct
16 Correct 738 ms 38892 KB Output is correct
17 Correct 2256 ms 168380 KB Output is correct
18 Correct 2519 ms 177560 KB Output is correct
19 Correct 2554 ms 177096 KB Output is correct
20 Correct 2410 ms 176564 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1088 ms 86088 KB Output is correct
13 Correct 806 ms 75268 KB Output is correct
14 Correct 1645 ms 172092 KB Output is correct
15 Correct 1756 ms 171784 KB Output is correct
16 Correct 1352 ms 168876 KB Output is correct
17 Correct 1597 ms 175672 KB Output is correct
18 Correct 1604 ms 171484 KB Output is correct
19 Correct 983 ms 28144 KB Output is correct
20 Correct 1342 ms 10652 KB Output is correct
21 Correct 677 ms 2068 KB Output is correct
22 Correct 1660 ms 16612 KB Output is correct
23 Correct 720 ms 38960 KB Output is correct
24 Correct 2189 ms 168372 KB Output is correct
25 Correct 2532 ms 177380 KB Output is correct
26 Correct 2442 ms 177200 KB Output is correct
27 Correct 2428 ms 176596 KB Output is correct
28 Runtime error 371 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1095 ms 86144 KB Output is correct
13 Correct 806 ms 75224 KB Output is correct
14 Correct 1641 ms 172004 KB Output is correct
15 Correct 1711 ms 171704 KB Output is correct
16 Correct 1449 ms 168900 KB Output is correct
17 Correct 1613 ms 175824 KB Output is correct
18 Correct 1647 ms 171508 KB Output is correct
19 Correct 948 ms 28180 KB Output is correct
20 Correct 1324 ms 10636 KB Output is correct
21 Correct 657 ms 2100 KB Output is correct
22 Correct 1639 ms 16572 KB Output is correct
23 Correct 732 ms 38856 KB Output is correct
24 Correct 2165 ms 168292 KB Output is correct
25 Correct 2516 ms 177368 KB Output is correct
26 Correct 2478 ms 177112 KB Output is correct
27 Correct 2405 ms 176576 KB Output is correct
28 Runtime error 379 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -