Submission #63789

#	Time	Username	Problem	Language	Result	Execution time	Memory
63789		mohammad_kilani	Game (IOI13_game)	C++17	80 / 100	10146 ms	257024 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 22001 , M = N * 30 * 19 + 10, L = N * 30;
int r1 , r2 , c1 , c2 ,r , c , rowscnt = 0 , colscnt = 0, tmp1 , tmp2;
int nxt2[L][2];
int nxt1[L];
long long val , seg[M];
int nxt3[M][2];

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;
}

inline int addrow(){
    nxt1[rowscnt] = -1;
    nxt2[rowscnt][0] = nxt2[rowscnt][1] = -1;
    return rowscnt++;
}

inline int addcol(){
    seg[colscnt] = 0;
    nxt3[colscnt][0] = nxt3[colscnt][1] = -1;
    return colscnt++;
}

void update_cols(int s,int e,int idx){
    if(s == e){
        seg[idx] = val;
        return;
    }
    if(c1 > ((s + e) >> 1)){
        if(nxt3[idx][1] == -1)
            nxt3[idx][1] = addcol();
        update_cols(((s+e) >> 1) + 1, e, nxt3[idx][1]);
    }
    else{
         if(nxt3[idx][0] == -1)
            nxt3[idx][0] = addcol();
        update_cols(s,((s+e) >> 1),nxt3[idx][0]);
    }
    seg[idx] = 0;
    if(nxt3[idx][0] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][0]]);
    if(nxt3[idx][1] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][1]]);
}

void update_cols_2(int s,int e,int idx,int l,int r){
    if(s == e){
        seg[idx] = 0;
        if(l != -1) seg[idx] = gcd2(seg[idx],seg[l]);
        if(r != -1) seg[idx] = gcd2(seg[idx],seg[r]);
        return ;
    }
    if(c1 > ((s + e) >> 1)){
        if(nxt3[idx][1] == -1)
            nxt3[idx][1] = addcol();
        update_cols_2(((s+e) >> 1) + 1 , e,nxt3[idx][1],(l == -1 ? -1 : nxt3[l][1]) , (r == -1 ? -1 : nxt3[r][1]));
    }
    else{
        if(nxt3[idx][0] == -1)
            nxt3[idx][0] = addcol();
        update_cols_2(s , ((s+e) >> 1) , nxt3[idx][0],(l == -1 ? -1 : nxt3[l][0]) , (r == -1 ? -1 : nxt3[r][0]));
    }
    seg[idx] = 0;
    if(nxt3[idx][0] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][0]]);
    if(nxt3[idx][1] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][1]]);

}

void update_cols_3(int s,int e,int idx,int l,int r){
    if(l == -1 && r == -1)
        return;
    if(s == e){
        seg[idx] = 0;
        if(l != -1) seg[idx] = gcd2(seg[idx],seg[l]);
        if(r != -1) seg[idx] = gcd2(seg[idx],seg[r]);
        return ;
    }
    if((l != -1 && nxt3[l][1] != -1) || (r != -1 && nxt3[r][1] != -1)){
        if(nxt3[idx][1] == -1)
            nxt3[idx][1] = addcol();
        update_cols_3(((s+e) >> 1) + 1 , e,nxt3[idx][1],(l == -1 ? -1 : nxt3[l][1]) , (r == -1 ? -1 : nxt3[r][1]));
    }
    if((l != -1 && nxt3[l][0] != -1) || (r != -1 && nxt3[r][0] != -1)){
        if(nxt3[idx][0] == -1)
            nxt3[idx][0] = addcol();
        update_cols_3(s , ((s+e) >> 1) , nxt3[idx][0],(l == -1 ? -1 : nxt3[l][0]) , (r == -1 ? -1 : nxt3[r][0]));
    }
    seg[idx] = 0;
    if(nxt3[idx][0] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][0]]);
    if(nxt3[idx][1] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][1]]);
}

void update_rows(int s,int e,int idx){
    if(s == e){
        if(nxt1[idx] == -1)
            nxt1[idx] = addcol();
        update_cols(0 , c , nxt1[idx]);
        return;
    }
    if(r1 > ((s + e) >> 1)){
        if(nxt2[idx][1] == -1)
            nxt2[idx][1] = addrow();
        update_rows(((s+e) >> 1) + 1, e,nxt2[idx][1]);
    }
    else{
        if(nxt2[idx][0] == -1)
            nxt2[idx][0] = addrow();
        update_rows(s , ((s+e) >> 1), nxt2[idx][0]);
    }
    if(nxt2[idx][0] == -1 || nxt2[idx][1] == -1) return;
    tmp1 = nxt2[idx][0];
    tmp2 = nxt2[idx][1];
    while((nxt2[tmp1][0] == -1) ^ (nxt2[tmp1][1] == -1)){
        if(nxt2[tmp1][0] == -1)
            tmp1 = nxt2[tmp1][1];
        else
            tmp1 = nxt2[tmp1][0];
    }
    if(tmp1 != -1)
        tmp1 = nxt1[tmp1];
    while((nxt2[tmp2][0] == -1) ^ (nxt2[tmp2][1] == -1)){
        if(nxt2[tmp2][0] == -1)
            tmp2 = nxt2[tmp2][1];
        else
            tmp2 = nxt2[tmp2][0];
    }
    if(tmp2 != -1)
        tmp2 = nxt1[tmp2];
    if(nxt1[idx] == -1){
        nxt1[idx] = addcol();
        update_cols_3(0, c , nxt1[idx], tmp1 , tmp2);
        return ;
    }
    update_cols_2(0 , c , nxt1[idx] , tmp1 , tmp2);
}

long long get_cols(int s,int e,int idx){
    if(s > c2 || e < c1 || idx == -1)
        return 0;
    if(s >= c1 && e <= c2)
        return seg[idx];
    return gcd2(get_cols(s,((s+e) >> 1),nxt3[idx][0]),get_cols(((s+e) >> 1) + 1, e,nxt3[idx][1]));
}

long long get_rows(int s,int e,int idx){
    if(s > r2 || e < r1 || idx == -1)
        return 0;
    if(s >= r1 && e <= r2){
        if((nxt2[idx][0] == -1) ^ (nxt2[idx][1] == -1)){
            if(nxt2[idx][1] == -1)
                return get_rows(s,((s+e) >> 1),nxt2[idx][0]);
            return get_rows(((s+e) >> 1) + 1, e,nxt2[idx][1]);
        }
        return get_cols(0 , c , nxt1[idx]);
    }
    return gcd2(get_rows(s,((s+e) >> 1),nxt2[idx][0]),get_rows(((s+e) >> 1) + 1, e,nxt2[idx][1]));
}


void init(int R, int C) {
    /*long double cur = sizeof(seg) + sizeof(nxt1) + sizeof(nxt2) + sizeof(nxt3);
    cur = cur / (1024.0 * 1024.0);
    cout << fixed << cur << endl;
    */
    r = R ;
    c = C;
    addrow();
}

void update(int P, int Q, long long K) {
    r1 = P;
    c1 = Q;
    val = K;
    update_rows(0 , r , 0);
}

long long calculate(int P, int Q, int U, int V) {
    r1 = P;
    r2 = U;
    c1 = Q;
    c2 = V;
    return get_rows(0 , r , 0);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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