Submission #281942

#	Time	Username	Problem	Language	Result	Execution time	Memory
281942		amoo_safar	Game (IOI13_game)	C++17	100 / 100	6278 ms	235736 KiB

game

#include "game.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Inf = 1e9 + 3;
const int LG = 30;
const int MX = 10010;
const int CNT = 198e5;
//int lc[CNT], rc[CNT]
int la = 1;
ll g[CNT];
int sn[CNT];

int ty;
int GetL(int id){
    ty = sn[id] & 7;
    if(ty == 0) return 0;
    if(ty == 1) return 0;
    if(ty == 2) return id + 1;
    if(ty == 3) return id + 1;
    if(ty == 4) return sn[id] >> 3;
    return -1;
}
int GetR(int id){
    ty = sn[id] & 7;
    if(ty == 0) return 0;
    if(ty == 1) return id + 1;
    if(ty == 2) return 0;
    if(ty == 3) return sn[id] >> 3;
    if(ty == 4) return id + 1;
    return -1;
}
void AddL(int id){
    ty = sn[id] & 7;
    if(ty >= 2) assert(false);
    if(ty == 0) ++la, sn[id] = 2;
    else sn[id] = 4 + (++ la) * 8;
}
void AddR(int id){
    ty = sn[id] & 7;
    if(ty == 1 || ty == 3 || ty == 4) assert(false);
    if(ty == 0) ++la, sn[id] = 1;
    else sn[id] = 3 + (++ la) * 8;
}

void Set(int id, int idx, ll val, int L, int R){
    if(L + 1 == R){
        g[id] = val;
        return ;
    }
    int mid = (L + R) >> 1;
    if(idx < mid){
        if(!GetL(id)) AddL(id); //lc[id] = ++la;
        Set(GetL(id), idx, val, L, mid);
    } else {
        if(!GetR(id)) AddR(id); //rc[id] = ++la;
        Set(GetR(id), idx, val, mid, R);
    }
    g[id] = __gcd(g[GetL(id)], g[GetR(id)]);
}

ll Get(int id, int l, int r, int L, int R){
    if(r <= L || R <= l) return 0;
    if(l <= L && R <= r) return g[id];
    int mid = (L + R) >> 1;
    return __gcd(GetL(id) ? Get(GetL(id), l, r, L, mid) : 0, GetR(id) ? Get(GetR(id), l, r, mid, R) : 0);
}

void Update(int id, int hl, int hr, int idx, int L, int R){
    if(L + 1 == R){
        g[id] = __gcd(g[hl], g[hr]);
        return ;
    }
    int mid = (L + R) >> 1;
    if(idx < mid){
        if(!GetL(id)) AddL(id);//lc[id] = ++la;
        Update(GetL(id), GetL(hl), GetL(hr), idx, L, mid);
    } else {
        if(!GetR(id)) AddR(id);//rc[id] = ++la;
        Update(GetR(id), GetR(hl), GetR(hr), idx, mid, R);
    }
    g[id] = __gcd(g[GetL(id)], g[GetR(id)]);
}

//Seg node[MX * LOG];

struct Seg2D {
    int ds;
    Seg2D *Lc, *Rc;
    Seg2D (){
        ds = 0;
        Lc = NULL;
        Rc = NULL;
    }
    void Set2D(int x, int y, ll val, int L, int R){
        if(L + 1 == R){
            if(!ds) ds = ++la;
            Set(ds, y, val, 0, Inf);
            return ;
        }
        int mid = (L + R) >> 1;
        if(x < mid){
            if(!Lc) Lc = new Seg2D();
            Lc -> Set2D(x, y, val, L, mid);
        } else {
            if(!Rc) Rc = new Seg2D();
            Rc -> Set2D(x, y, val, mid, R);
        }
        if(!ds) ds = ++la;
        Update(ds, Lc ? Lc -> ds : 0, Rc ? Rc -> ds : 0, y, 0, Inf);
    }
    ll Get2D(int lx, int rx, int ly, int ry, int L, int R){
        if(rx <= L || R <= lx) return 0;
        if(lx <= L && R <= rx){
            if(ds == 0) return 0;
            return Get(ds, ly, ry, 0, Inf);
        }
        int mid = (L + R) >> 1;
        return __gcd(Lc ? Lc -> Get2D(lx, rx, ly, ry, L, mid) : 0, Rc ? Rc -> Get2D(lx, rx, ly, ry, mid, R) : 0);
    }
};
Seg2D Board;

void init(int R, int C) {
    assert(R <= Inf);
    assert(C <= Inf);
}

void update(int P, int Q, ll K) {
    Board.Set2D(P, Q, K, 0, Inf);
}

ll calculate(int P, int Q, int U, int V) {
    return Board.Get2D(P, U + 1, Q, V + 1, 0, Inf);
}

Compilation message (stderr)

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

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