oj.uz

Submission #1032492

# Submission time Handle Problem Language Result Execution time Memory
1032492 2024-07-23T21:03:06 Z noyancanturk Game (IOI13_game) C++17
80 / 100
 13000 ms 121744 KB 
#include "game.h"
    
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
    
#include<bits/stdc++.h>
using namespace std;
    
int L,R;
long long ANS;
int n,m;
int P;
long long VAL;
struct treap {
    struct Node{
        long long val=0,all=0;
        int ind=0,pri=rand(),l,r;
        Node*lc=0,*rc=0;
        Node(){}
        Node(long long VAL,int IND){
            val=all=VAL;
            ind=l=r=IND;
        }
    };
    using pnode=Node*;
    pnode root=new Node(0,0);
    #define cur tree[node]
    void query(pnode p){
        if(!p)return;
        if(p->r<L||R<p->l)return;
        if(L<=p->l&&p->r<=R){
            ANS=gcd2(ANS,p->all);
            return;
        }
        if(L<=p->ind&&p->ind<=R){
            ANS=gcd2(ANS,p->val);
        }
        if(L<=p->ind)query(p->lc);
        if(p->ind<=R)query(p->rc);
    }
    void query(){query(root);};
    long long pquery(pnode p){
        if(!p)return 0;
        if(p->ind==P)return p->val;
        if(P<p->ind)return pquery(p->lc);
        return pquery(p->rc);
    }
    long long pquery(){return pquery(root);}
    void upd(pnode p){
        if(!p)return;
        p->all=gcd2(p->val,gcd2(p->lc?p->lc->all:0,p->rc?p->rc->all:0));
        p->l=min(p->ind,p->lc?p->lc->l:0);
        p->r=max(p->ind,p->rc?p->rc->r:0);
    }
    void split(pnode p,pnode&l,pnode&r,int ind){
        if(!p){
            l=r=0;
            return;
        }
        if(p->ind<ind){
            split(p->rc,p->rc,r,ind);
            l=p;
        }else{
            split(p->lc,l,p->lc,ind);
            r=p;
        }
        upd(p);
    }
    void merge(pnode&p,pnode l,pnode r){
        if(!l){
            p=r;
            return;
        }
        if(!r){
            p=l;
            return;
        }
        if(r->pri<l->pri){
            merge(l->rc,l->rc,r);
            p=l;
        }else{
            merge(r->lc,l,r->lc);
            p=r;
        }
        upd(p);
    }
    void update(long long val){
        pnode t1,t2,t3;
        t1=t2=t3=0;
        split(root,t1,t2,P);
        split(t2,t2,t3,P+1);
        if(t2){
            t2->val=t2->all=val;
        }else{
            t2=new Node(val,P);
        }
        merge(root,t1,t2);
        merge(root,root,t3);
    }
};
    
struct {
    struct {
        treap sst;
        int ch[2]{0,0};
    }subtree[1000000];
    int nxx=1;
    void init(int N,int M){
        n=N,m=M;
    }
    int P1;
    void update(int l,int r,int&node){
        if(!node){
            node=++nxx;
        }
        if(l==r){
            subtree[node].sst.update(VAL);
            return;
        }
        int mid=(l+r)>>1;
        if(P1<=mid){
            update(l,mid,subtree[node].ch[0]);
        }else{
            update(mid+1,r,subtree[node].ch[1]);
        }
        subtree[node].sst.update(gcd2(subtree[subtree[node].ch[0]].sst.pquery(),subtree[subtree[node].ch[1]].sst.pquery()));
    }
    void update(int p1,int p2,long long val){
        P1=p1,P=p2,VAL=val;
        L=R=P;
        int root=1;
        update(0,n-1,root);
    }
    int L1,R1;
    void query(int l,int r,int node){
        if(L1<=l&&r<=R1){
            subtree[node].sst.query();
            return;
        }
        if(r<L1||R1<l)return;
        int mid=(l+r)>>1;
        if(subtree[node].ch[0])query(l,mid,subtree[node].ch[0]);
        if(subtree[node].ch[1])query(mid+1,r,subtree[node].ch[1]);
    }
    long long query(int l1,int r1,int l2,int r2){
        L1=l1,R1=r1,L=l2,R=r2;
        ANS=0;
        query(0,n-1,1);
        return ANS;
    }
}st;
    
void init(int R, int C) {
    st.init(R,C);
}
    
void update(int P, int Q, long long K) {
    st.update(P,Q,K);
}
    
long long calculate(int P, int Q, int U, int V) {
    long long val=st.query(P,U,Q,V);
    return val;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 78672 KB Output is correct
2 Correct 44 ms 78544 KB Output is correct
3 Correct 46 ms 78676 KB Output is correct
4 Correct 43 ms 78672 KB Output is correct
5 Correct 44 ms 78500 KB Output is correct
6 Correct 42 ms 78676 KB Output is correct
7 Correct 44 ms 78680 KB Output is correct
8 Correct 47 ms 78708 KB Output is correct
9 Correct 47 ms 78528 KB Output is correct
10 Correct 49 ms 78580 KB Output is correct
11 Correct 44 ms 78672 KB Output is correct
12 Correct 50 ms 78676 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 78576 KB Output is correct
2 Correct 46 ms 78716 KB Output is correct
3 Correct 44 ms 78676 KB Output is correct
4 Correct 3613 ms 89096 KB Output is correct
5 Correct 2875 ms 88888 KB Output is correct
6 Correct 980 ms 86184 KB Output is correct
7 Correct 1685 ms 86028 KB Output is correct
8 Correct 353 ms 85072 KB Output is correct
9 Correct 1309 ms 86036 KB Output is correct
10 Correct 1645 ms 85592 KB Output is correct
11 Correct 42 ms 78676 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 78676 KB Output is correct
2 Correct 43 ms 78676 KB Output is correct
3 Correct 40 ms 78672 KB Output is correct
4 Correct 43 ms 78624 KB Output is correct
5 Correct 41 ms 78604 KB Output is correct
6 Correct 44 ms 78676 KB Output is correct
7 Correct 42 ms 78684 KB Output is correct
8 Correct 41 ms 78676 KB Output is correct
9 Correct 41 ms 78672 KB Output is correct
10 Correct 42 ms 78676 KB Output is correct
11 Correct 40 ms 78684 KB Output is correct
12 Correct 4707 ms 90780 KB Output is correct
13 Correct 3334 ms 85236 KB Output is correct
14 Correct 233 ms 83028 KB Output is correct
15 Correct 3500 ms 86652 KB Output is correct
16 Correct 191 ms 88964 KB Output is correct
17 Correct 748 ms 86868 KB Output is correct
18 Correct 1803 ms 89924 KB Output is correct
19 Correct 1326 ms 90196 KB Output is correct
20 Correct 1290 ms 89680 KB Output is correct
21 Correct 46 ms 78448 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 78676 KB Output is correct
2 Correct 46 ms 78680 KB Output is correct
3 Correct 44 ms 78676 KB Output is correct
4 Correct 46 ms 78484 KB Output is correct
5 Correct 46 ms 78616 KB Output is correct
6 Correct 60 ms 78672 KB Output is correct
7 Correct 51 ms 78676 KB Output is correct
8 Correct 44 ms 78532 KB Output is correct
9 Correct 43 ms 78636 KB Output is correct
10 Correct 42 ms 78676 KB Output is correct
11 Correct 46 ms 78676 KB Output is correct
12 Correct 3809 ms 89212 KB Output is correct
13 Correct 3201 ms 88904 KB Output is correct
14 Correct 994 ms 86240 KB Output is correct
15 Correct 1742 ms 85840 KB Output is correct
16 Correct 354 ms 85020 KB Output is correct
17 Correct 1328 ms 86104 KB Output is correct
18 Correct 1764 ms 85552 KB Output is correct
19 Correct 4968 ms 90844 KB Output is correct
20 Correct 3363 ms 85332 KB Output is correct
21 Correct 204 ms 83152 KB Output is correct
22 Correct 3555 ms 86452 KB Output is correct
23 Correct 206 ms 88912 KB Output is correct
24 Correct 707 ms 86868 KB Output is correct
25 Correct 1729 ms 89936 KB Output is correct
26 Correct 1348 ms 90020 KB Output is correct
27 Correct 1180 ms 89424 KB Output is correct
28 Correct 2810 ms 106988 KB Output is correct
29 Correct 6335 ms 109532 KB Output is correct
30 Correct 5944 ms 102012 KB Output is correct
31 Correct 4367 ms 97756 KB Output is correct
32 Correct 276 ms 86352 KB Output is correct
33 Correct 402 ms 84556 KB Output is correct
34 Correct 247 ms 102200 KB Output is correct
35 Correct 882 ms 94540 KB Output is correct
36 Correct 2357 ms 104532 KB Output is correct
37 Correct 1575 ms 104788 KB Output is correct
38 Correct 1591 ms 104136 KB Output is correct
39 Correct 1264 ms 99928 KB Output is correct
40 Correct 47 ms 78680 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 78676 KB Output is correct
2 Correct 46 ms 78672 KB Output is correct
3 Correct 44 ms 78668 KB Output is correct
4 Correct 47 ms 78676 KB Output is correct
5 Correct 46 ms 78676 KB Output is correct
6 Correct 46 ms 78676 KB Output is correct
7 Correct 46 ms 78564 KB Output is correct
8 Correct 50 ms 78672 KB Output is correct
9 Correct 46 ms 78676 KB Output is correct
10 Correct 57 ms 78676 KB Output is correct
11 Correct 46 ms 78672 KB Output is correct
12 Correct 4022 ms 85328 KB Output is correct
13 Correct 3088 ms 85672 KB Output is correct
14 Correct 989 ms 82256 KB Output is correct
15 Correct 1728 ms 82076 KB Output is correct
16 Correct 329 ms 81492 KB Output is correct
17 Correct 1280 ms 82264 KB Output is correct
18 Correct 1645 ms 81688 KB Output is correct
19 Correct 4908 ms 87564 KB Output is correct
20 Correct 3322 ms 81988 KB Output is correct
21 Correct 221 ms 79100 KB Output is correct
22 Correct 3392 ms 82632 KB Output is correct
23 Correct 192 ms 85328 KB Output is correct
24 Correct 708 ms 82900 KB Output is correct
25 Correct 1649 ms 85696 KB Output is correct
26 Correct 1304 ms 85840 KB Output is correct
27 Correct 1237 ms 85076 KB Output is correct
28 Correct 2800 ms 98532 KB Output is correct
29 Correct 6652 ms 101548 KB Output is correct
30 Correct 6719 ms 96468 KB Output is correct
31 Correct 4631 ms 92276 KB Output is correct
32 Correct 261 ms 79188 KB Output is correct
33 Correct 396 ms 79696 KB Output is correct
34 Correct 236 ms 98644 KB Output is correct
35 Correct 833 ms 89428 KB Output is correct
36 Correct 2392 ms 99092 KB Output is correct
37 Correct 1603 ms 99056 KB Output is correct
38 Correct 1677 ms 98640 KB Output is correct
39 Correct 6647 ms 121744 KB Output is correct
40 Execution timed out 13040 ms 116624 KB Time limit exceeded
41 Halted 0 ms 0 KB -