oj.uz

Submission #1032479

# Submission time Handle Problem Language Result Execution time Memory
1032479 2024-07-23T20:29:29 Z noyancanturk Game (IOI13_game) C++17
0 / 100
 55 ms 78728 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);}
    int getl(pnode p){
        if(p)return p->l;
        return 2000000000;
    }
    int getr(pnode p){
        if(p)return p->r;
        return -1;
    }
    int getall(pnode p){
        if(p)return p->all;
        return 0;
    }
    void upd(pnode p){
        if(!p)return;
        p->all=gcd2(p->all,gcd2(getall(p->lc),getall(p->rc)));
        p->l=min(p->ind,getl(p->lc));
        p->r=max(p->ind,getr(p->rc));
    }
    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 78668 KB Output is correct
2 Incorrect 55 ms 78672 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 78676 KB Output is correct
2 Incorrect 49 ms 78592 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 78680 KB Output is correct
2 Incorrect 45 ms 78728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 78672 KB Output is correct
2 Incorrect 53 ms 78596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 78604 KB Output is correct
2 Incorrect 45 ms 78692 KB Output isn't correct
3 Halted 0 ms 0 KB -