Submission #854049

#	Time	Username	Problem	Language	Result	Execution time	Memory
854049		abcvuitunggio	Game (IOI13_game)	C++17	37 / 100	13097 ms	22468 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
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;
}
vector <long long> st,ul,ur,dl,dr;
void gen(){
    st.emplace_back(0);
    ul.emplace_back(-1);
    ur.emplace_back(-1);
    dl.emplace_back(-1);
    dr.emplace_back(-1);
}
void update(int node, int l, int r, int l2, int r2, int i, int j, long long val){
    if (l>i||r<i||l2>j||r2<j||l>r||l2>r2)
        return;
    if (l==r&&l2==r2){
        st[node]=val;
        return;
    }
    int mid=(l+r)>>1,mid2=(l2+r2)>>1;
    if (ul[node]==-1){
        ul[node]=st.size();
        gen();
    }
    if (ur[node]==-1){
        ur[node]=st.size();
        gen();
    }
    if (dl[node]==-1){
        dl[node]=st.size();
        gen();
    }
    if (dr[node]==-1){
        dr[node]=st.size();
        gen();
    }
    update(ul[node],l,mid,l2,mid2,i,j,val);
    update(ur[node],l,mid,mid2+1,r2,i,j,val);
    update(dl[node],mid+1,r,l2,mid2,i,j,val);
    update(dr[node],mid+1,r,mid2+1,r2,i,j,val);
    st[node]=gcd2(gcd2(gcd2(st[ul[node]],st[ur[node]]),st[dl[node]]),st[dr[node]]);
}
long long get(int node, int l, int r, int l2, int r2, int i, int j, int u, int v){
    if (node==-1||l>j||r<i||l2>v||r2<u||l>r||l2>r2)
        return 0;
    if (l>=i&&r<=j&&l2>=u&&r2<=v)
        return st[node];
    int mid=(l+r)>>1,mid2=(l2+r2)>>1;
    long long a=get(ul[node],l,mid,l2,mid2,i,j,u,v);
    long long b=get(ur[node],l,mid,mid2+1,r2,i,j,u,v);
    long long c=get(dl[node],mid+1,r,l2,mid2,i,j,u,v);
    long long d=get(dr[node],mid+1,r,mid2+1,r2,i,j,u,v);
    return gcd2(gcd2(gcd2(a,b),c),d);
}
int r,c;
void init(int R, int C){
    st.reserve(80000000);
    gen();
    r=R;
    c=C;
}
void update(int P, int Q, long long K) {
    update(0,0,r-1,0,c-1,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
    return get(0,0,r-1,0,c-1,P,U,Q,V);
}

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