Submission #854082

#	Time	Username	Problem	Language	Result	Execution time	Memory
854082		abcvuitunggio	Game (IOI13_game)	C++17	80 / 100	3575 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=2650000;
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;
}
static int r,c,lx[sz],rx[sz],id;
static vector <vector <long long>> st;
static vector <vector <int>> ly,ry;
static void gen(int i){
    if (i>=st.size()){
        st.emplace_back();
        ly.emplace_back();
        ry.emplace_back();
    }
    st[i].emplace_back(0);
    ly[i].emplace_back(-1);
    ry[i].emplace_back(-1);
}
static void update2(int node, int node2, int l2, int r2, int j, long long val){
    if (node2==-1||l2>j||r2<j||l2>r2)
        return;
    if (l2==r2){
        st[node][node2]=val;
        return;
    }
    int mid=(l2+r2)>>1;
    if (mid>=j){
        if (ly[node][node2]==-1){
            ly[node][node2]=st[node].size();
            gen(node);
        }
        update2(node,ly[node][node2],l2,mid,j,val);
    }
    else{
        if (ry[node][node2]==-1){
            ry[node][node2]=st[node].size();
            gen(node);
        }
        update2(node,ry[node][node2],mid+1,r2,j,val);
    }
    st[node][node2]=gcd2((ly[node][node2]==-1?0:st[node][ly[node][node2]]),(ry[node][node2]==-1?0:st[node][ry[node][node2]]));
}
static long long get2(int node, int node2, int l, int r, int u, int v){
    if (node2==-1||l>v||r<u||l>r)
        return 0;
    if (l>=u&&r<=v)
        return st[node][node2];
    int mid=(l+r)>>1;
    return gcd2(get2(node,ly[node][node2],l,mid,u,v),get2(node,ry[node][node2],mid+1,r,u,v));
}
static void update(int node, int l, int r, int i, int j, long long val){
    if (node==-1||l>i||r<i||l>r)
        return;
    if (l==r){
        update2(node,0,0,c-1,j,val);
        return;
    }
    int mid=(l+r)>>1;
    if (mid>=i){
        if (lx[node]==-1){
            id++;
            lx[node]=id;
            gen(id);
        }
        update(lx[node],l,mid,i,j,val);
    }
    else{
        if (rx[node]==-1){
            id++;
            rx[node]=id;
            gen(id);
        }
        update(rx[node],mid+1,r,i,j,val);
    }
    update2(node,0,0,c-1,j,gcd2((lx[node]==-1?0:get2(lx[node],0,0,c-1,j,j)),(rx[node]==-1?0:get2(rx[node],0,0,c-1,j,j))));
}
long long get(int node, int l, int r, int i, int j, int u, int v){
    if (node==-1||l>j||r<i||l>r)
        return 0;
    if (l>=i&&r<=j)
        return get2(node,0,0,c-1,u,v);
    int mid=(l+r)>>1;
    return gcd2(get(lx[node],l,mid,i,j,u,v),get(rx[node],mid+1,r,i,j,u,v));
}
void init(int R, int C){
    memset(lx,-1,sizeof(lx));
    memset(rx,-1,sizeof(rx));
    st.reserve(sz);
    ly.reserve(sz);
    ry.reserve(sz);
    gen(0);
    r=R;
    c=C;
}
void update(int P, int Q, long long K){
    update(0,0,r-1,P,Q,K);
}
long long calculate(int P, int Q, int U, int V){
    return get(0,0,r-1,P,U,Q,V);
}

Compilation message (stderr)

game.cpp: In function 'void gen(int)':
game.cpp:18:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     if (i>=st.size()){
      |         ~^~~~~~~~~~~

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