Submission #1032110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032110		noyancanturk	Game (IOI13_game)	C++17	80 / 100	1551 ms	256000 KiB

game

#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<iostream>
struct Nd{
    long long val=0;
    int ch[2]{0,0};
}tree[19800000];
int nx=1;
int L,R;
long long ANS;
int n,m;
int P;
long long VAL;
struct segtree {
    int root;
    void update(int l,int r,int&node){
        if(!node){
            node=nx++;
        }
        if(l==r){
            tree[node].val=VAL;
            return;
        }
        int mid=(l+r)>>1;
        if(P<=mid){
            update(l,mid,tree[node].ch[0]);
        }else{
            update(mid+1,r,tree[node].ch[1]);
        }
        tree[node].val=gcd2(tree[tree[node].ch[0]].val,tree[tree[node].ch[1]].val);
    }
    void update(int p,long long val){
        P=p;
        update(0,m-1,root);
    }
    void insert(int l,int r,int&node,int node1,int node2){
        if(!node){
            node=nx++;
        }
        tree[node].val=gcd2(tree[node1].val,tree[node2].val);
        if(l==r)return;
        int mid=(l+r)>>1;
        if(P<=mid){
            insert(l,mid,tree[node].ch[0],tree[node1].ch[0],tree[node2].ch[0]);
        }else{
            insert(mid+1,r,tree[node].ch[1],tree[node1].ch[1],tree[node2].ch[1]);
        }
    }
    void insert(int p,int node1,int node2){
        P=p;
        insert(0,m-1,root,node1,node2);
    }
    void query(int l,int r,int node){
        if(L<=l&r<=R){
            ANS=gcd2(ANS,tree[node].val);
            return;
        }
        if(r<L||R<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]);
    }
    void query(int l,int r){
        L=l,R=r;
        query(0,m-1,root);
    }
};

struct {
    struct {
        segtree sst;
        int ch[2]{0,0};
    }subtree[1000000];
    int nxx=1;
    void init(int N,int M){
        n=N,m=M;
    }
    int P1,P2;
    void update(int l,int r,int&node){
        if(!node){
            node=++nxx;
        }
        if(l==r){
            subtree[node].sst.update(P2,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.insert(P2,subtree[subtree[node].ch[0]].sst.root,subtree[subtree[node].ch[1]].sst.root);
    }
    void update(int p1,int p2,long long val){
        P1=p1,P2=p2,VAL=val;
        int root=1;
        update(0,n-1,root);
    }
    int L1,R1,L2,R2;
    void query(int l,int r,int node){
        if(L1<=l&&r<=R1){
            subtree[node].sst.query(L2,R2);
            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,L2=l2,R2=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;
}

Compilation message (stderr)

game.cpp: In member function 'void segtree::query(int, int, int)':
game.cpp:64:13: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   64 |         if(L<=l&r<=R){
      |            ~^~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 0 / 20