Submission #767589

#	Time	Username	Problem	Language	Result	Execution time	Memory
767589		Ahmed57	Game (IOI13_game)	C++17	63 / 100	1300 ms	202912 KiB

game

#include "game.h"
#include<bits/stdc++.h>

using namespace std;
int n,m;
vector<vector<long long>> t;
void init(int R, int C){
    n = R , m = C;t.clear();
    vector<long long> a;
    bool ss = 0;
    if(R<=2000&&R>=100&&C<=2000&&C>=100){
        ss = 1;
    }
    long long hC = 4*C;
    long long hR = 4*R;
    if(ss)hC = min(hC,5000LL);
    if(ss)hR = min(hR,5000LL);
    for(int i = 0;i<hC;i++)a.push_back(0);
    for(int i = 0;i<hR;i++)t.push_back(a);
}
void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, long long new_val) {
    if (ly == ry) {
        if (lx == rx)
            t[vx][vy] = new_val;
        else
            t[vx][vy] = __gcd(t[vx*2][vy] , t[vx*2+1][vy]);
    } else {
        int my = (ly + ry) / 2;
        if (y <= my)
            update_y(vx, lx, rx, vy*2, ly, my, x, y, new_val);
        else
            update_y(vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
        t[vx][vy] = __gcd(t[vx][vy*2] , t[vx][vy*2+1]);
    }
}

void update_x(int vx, int lx, int rx, int x, int y, long long new_val) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        if (x <= mx)
            update_x(vx*2, lx, mx, x, y, new_val);
        else
            update_x(vx*2+1, mx+1, rx, x, y, new_val);
    }
    update_y(vx, lx, rx, 1, 1, m, x, y, new_val);
}
void update(int P, int Q, long long K){
    P++;Q++;
    update_x(1,1,n,P,Q,K);
}
long long sum_y(int vx, int vy, int tly, int try_, int ly, int ry) {
    if (ly > ry)
        return 0;
    if (ly == tly && try_ == ry)
        return t[vx][vy];
    int tmy = (tly + try_) / 2;
    return __gcd(sum_y(vx, vy*2, tly, tmy, ly, min(ry, tmy))
         , sum_y(vx, vy*2+1, tmy+1, try_, max(ly, tmy+1), ry));
}

long long sum_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
    if (lx > rx)
        return 0;
    if (lx == tlx && trx == rx)
        return sum_y(vx, 1, 1,  m, ly, ry);
    int tmx = (tlx + trx) / 2;
    return __gcd(sum_x(vx*2, tlx, tmx, lx, min(rx, tmx), ly, ry)
         , sum_x(vx*2+1, tmx+1, trx, max(lx, tmx+1), rx, ly, ry));
}
long long calculate(int P, int Q, int U, int V){
    return sum_x(1,1,n,P+1,U+1,Q+1,V+1);
}
/*
int main(){
    init(2,3);
    update(0,0,20);
    update(0,2,15);
    update(1,1,12);
    cout<<calculate(0,0,0,2)<<endl;
    cout<<calculate(0,0,1,1)<<endl;
}*/

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