oj.uz

Submission #1032487

# Submission time Handle Problem Language Result Execution time Memory
1032487 2024-07-23T20:56:28 Z noyancanturk Game (IOI13_game) C++17
100 / 100
 2684 ms 108060 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();
        Node*lc=0,*rc=0;
        Node(){}
        Node(long long VAL,int IND){
            val=all=VAL;
            ind=IND;
        }
    };
    using pnode=Node*;
    pnode root=new Node(0,0);
    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));
    }
    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 query(){
        pnode t1,t2,t3;
        t1=t2=t3=0;
        split(root,t1,t2,L);
        split(t2,t2,t3,R+1);
        if(t2){
            ANS=gcd2(ANS,t2->all);
        }
        merge(root,t1,t2);
        merge(root,root,t3);
    }
    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 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 tr;
        int ch[2]{0,0};
    }tree[1000000];
    int nxx=1;
    void init(int N,int M){
        n=N,m=M;
    }
    int P1;
    long long update(int l,int r,int&node){
        if(!node){
            node=++nxx;
        }
        if(l==r){
            tree[node].tr.update(VAL);
            return VAL;
        }
        int mid=(l+r)>>1;
        long long huh=0;
        if(P1<=mid){
            huh=update(l,mid,tree[node].ch[0]);
            if(tree[node].ch[1])huh=gcd2(huh,tree[tree[node].ch[1]].tr.pquery());
        }else{
            huh=update(mid+1,r,tree[node].ch[1]);
            if(tree[node].ch[0])huh=gcd2(huh,tree[tree[node].ch[0]].tr.pquery());
        }
        tree[node].tr.update(huh);
        return huh;
    }
    void update(int p1,int p2,long long val){
        P1=p1,P=p2,VAL=val;
        int root=1;
        update(0,n-1,root);
    }
    int L1,R1;
    void query(int l,int r,int node){
        if(L1<=l&&r<=R1){
            tree[node].tr.query();
            return;
        }
        if(r<L1||R1<l)return;
        int mid=(l+r)>>1;
        if(tree[node].ch[0])query(l,mid,tree[node].ch[0]);
        if(tree[node].ch[1])query(mid+1,r,tree[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 42 ms 62800 KB Output is correct
2 Correct 44 ms 63060 KB Output is correct
3 Correct 55 ms 63056 KB Output is correct
4 Correct 43 ms 62804 KB Output is correct
5 Correct 43 ms 62816 KB Output is correct
6 Correct 45 ms 63056 KB Output is correct
7 Correct 41 ms 63068 KB Output is correct
8 Correct 41 ms 62952 KB Output is correct
9 Correct 41 ms 62936 KB Output is correct
10 Correct 44 ms 62800 KB Output is correct
11 Correct 41 ms 63056 KB Output is correct
12 Correct 42 ms 62804 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 62800 KB Output is correct
2 Correct 41 ms 62984 KB Output is correct
3 Correct 50 ms 62944 KB Output is correct
4 Correct 547 ms 73440 KB Output is correct
5 Correct 267 ms 73152 KB Output is correct
6 Correct 679 ms 70736 KB Output is correct
7 Correct 796 ms 70604 KB Output is correct
8 Correct 533 ms 69716 KB Output is correct
9 Correct 776 ms 70608 KB Output is correct
10 Correct 613 ms 70228 KB Output is correct
11 Correct 51 ms 62800 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 62848 KB Output is correct
2 Correct 43 ms 63060 KB Output is correct
3 Correct 44 ms 62940 KB Output is correct
4 Correct 45 ms 62804 KB Output is correct
5 Correct 54 ms 62800 KB Output is correct
6 Correct 44 ms 63060 KB Output is correct
7 Correct 43 ms 62800 KB Output is correct
8 Correct 46 ms 62804 KB Output is correct
9 Correct 42 ms 63060 KB Output is correct
10 Correct 41 ms 63056 KB Output is correct
11 Correct 59 ms 63056 KB Output is correct
12 Correct 805 ms 74576 KB Output is correct
13 Correct 1385 ms 69556 KB Output is correct
14 Correct 348 ms 68264 KB Output is correct
15 Correct 1427 ms 70736 KB Output is correct
16 Correct 205 ms 72276 KB Output is correct
17 Correct 1130 ms 71508 KB Output is correct
18 Correct 1813 ms 73748 KB Output is correct
19 Correct 1609 ms 73832 KB Output is correct
20 Correct 1483 ms 73404 KB Output is correct
21 Correct 43 ms 62856 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 62824 KB Output is correct
2 Correct 42 ms 63060 KB Output is correct
3 Correct 43 ms 63064 KB Output is correct
4 Correct 46 ms 62800 KB Output is correct
5 Correct 42 ms 62844 KB Output is correct
6 Correct 41 ms 63060 KB Output is correct
7 Correct 43 ms 62812 KB Output is correct
8 Correct 41 ms 62804 KB Output is correct
9 Correct 41 ms 63060 KB Output is correct
10 Correct 41 ms 62804 KB Output is correct
11 Correct 42 ms 63068 KB Output is correct
12 Correct 520 ms 73300 KB Output is correct
13 Correct 229 ms 73276 KB Output is correct
14 Correct 695 ms 70740 KB Output is correct
15 Correct 779 ms 70484 KB Output is correct
16 Correct 541 ms 69828 KB Output is correct
17 Correct 777 ms 70480 KB Output is correct
18 Correct 617 ms 69972 KB Output is correct
19 Correct 745 ms 74580 KB Output is correct
20 Correct 1248 ms 69456 KB Output is correct
21 Correct 280 ms 68180 KB Output is correct
22 Correct 1440 ms 70764 KB Output is correct
23 Correct 203 ms 72272 KB Output is correct
24 Correct 1156 ms 71504 KB Output is correct
25 Correct 1868 ms 73684 KB Output is correct
26 Correct 1656 ms 73936 KB Output is correct
27 Correct 1467 ms 73492 KB Output is correct
28 Correct 700 ms 88660 KB Output is correct
29 Correct 1149 ms 91220 KB Output is correct
30 Correct 1780 ms 83284 KB Output is correct
31 Correct 1534 ms 80208 KB Output is correct
32 Correct 315 ms 72784 KB Output is correct
33 Correct 504 ms 73040 KB Output is correct
34 Correct 248 ms 84876 KB Output is correct
35 Correct 1231 ms 81240 KB Output is correct
36 Correct 2281 ms 89168 KB Output is correct
37 Correct 1757 ms 89292 KB Output is correct
38 Correct 1829 ms 88772 KB Output is correct
39 Correct 1510 ms 85472 KB Output is correct
40 Correct 36 ms 62800 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62804 KB Output is correct
2 Correct 38 ms 63056 KB Output is correct
3 Correct 37 ms 63064 KB Output is correct
4 Correct 37 ms 63040 KB Output is correct
5 Correct 36 ms 62852 KB Output is correct
6 Correct 37 ms 63056 KB Output is correct
7 Correct 39 ms 62812 KB Output is correct
8 Correct 38 ms 62804 KB Output is correct
9 Correct 40 ms 63056 KB Output is correct
10 Correct 37 ms 63056 KB Output is correct
11 Correct 49 ms 63056 KB Output is correct
12 Correct 475 ms 73300 KB Output is correct
13 Correct 223 ms 73296 KB Output is correct
14 Correct 620 ms 70748 KB Output is correct
15 Correct 701 ms 70296 KB Output is correct
16 Correct 472 ms 69768 KB Output is correct
17 Correct 670 ms 70400 KB Output is correct
18 Correct 580 ms 70228 KB Output is correct
19 Correct 735 ms 74800 KB Output is correct
20 Correct 1226 ms 69528 KB Output is correct
21 Correct 244 ms 68448 KB Output is correct
22 Correct 1270 ms 70644 KB Output is correct
23 Correct 198 ms 72244 KB Output is correct
24 Correct 1055 ms 71508 KB Output is correct
25 Correct 1734 ms 73772 KB Output is correct
26 Correct 1536 ms 73872 KB Output is correct
27 Correct 1332 ms 73272 KB Output is correct
28 Correct 636 ms 88664 KB Output is correct
29 Correct 1100 ms 91068 KB Output is correct
30 Correct 1651 ms 83504 KB Output is correct
31 Correct 1509 ms 80332 KB Output is correct
32 Correct 294 ms 72784 KB Output is correct
33 Correct 518 ms 72940 KB Output is correct
34 Correct 249 ms 84952 KB Output is correct
35 Correct 1187 ms 81104 KB Output is correct
36 Correct 2133 ms 89036 KB Output is correct
37 Correct 1724 ms 89152 KB Output is correct
38 Correct 1645 ms 88552 KB Output is correct
39 Correct 784 ms 105920 KB Output is correct
40 Correct 1758 ms 108060 KB Output is correct
41 Correct 2444 ms 98792 KB Output is correct
42 Correct 2115 ms 91772 KB Output is correct
43 Correct 391 ms 102992 KB Output is correct
44 Correct 428 ms 73552 KB Output is correct
45 Correct 1472 ms 85588 KB Output is correct
46 Correct 2676 ms 106936 KB Output is correct
47 Correct 2684 ms 106880 KB Output is correct
48 Correct 2366 ms 106604 KB Output is correct
49 Correct 40 ms 62800 KB Output is correct