Submission #766028

#	Time	Username	Problem	Language	Result	Execution time	Memory
766028		fatemetmhr	Game (IOI13_game)	C++17	100 / 100	5297 ms	128576 KiB

game

//  ~ Be Name Khoda ~  //
 
#include "game.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
 
using namespace std;
 
typedef long long ll;
 
#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
 
const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  2e7;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int tt = 0;
 
 
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;
}
 
namespace seg{
    int n, m, newnode = 2, innernode = 2, inner[maxnt];
    int chil[maxnt][2], innerchil[maxnt][2];
    ll g[maxnt];
    void innerupdbase(int l, int r, int id, ll val, int v){
        //cout << "inner upd with " << l << ' ' << r << ' ' << id << ' ' << val << ' ' << v << endl;
        if(r - l == 1){
            g[v] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if(id < mid){
            if(!innerchil[v][0])
                innerchil[v][0] = innernode++;
            innerupdbase(l, mid, id, val, innerchil[v][0]);
        }
        else{
            if(!innerchil[v][1])
                innerchil[v][1] = innernode++;
            innerupdbase(mid, r, id, val, innerchil[v][1]);
        }
        g[v] = gcd2(g[innerchil[v][0]], g[innerchil[v][1]]);
        //cout << "ok " << l << ' ' << r << ' ' << val << ' ' << v << ' ' << g[v] << ' ' << g[innerchil[v][1]] << ' ' << g[innerchil[v][0]] << endl;
    }
 
    void innerupdult(int l, int r, int id, int v1, int v2, int v3){
        g[v1] = gcd2(g[v2], g[v3]);
        if(r - l == 1)
            return;
        int mid = (l + r) >> 1;
        if(id < mid){
            if(!innerchil[v1][0])
                innerchil[v1][0] = innernode++;
            innerupdult(l, mid, id, innerchil[v1][0], innerchil[v2][0], innerchil[v3][0]);
        }
        else{
            if(!innerchil[v1][1])
                innerchil[v1][1] = innernode++;
            innerupdult(mid, r, id, innerchil[v1][1], innerchil[v2][1], innerchil[v3][1]);
        }
    }
 
 
    ll innerget(int l, int r, int lq, int rq, int v){
        if(v == 0 || rq <= l || r <= lq)
            return 0;
        if(lq <= l && r <= rq){
            //cout << "inner getting " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << g[v] << endl;
            return g[v];
        }
        int mid = (l + r) >> 1;
        return gcd2(innerget(l, mid, lq, rq, innerchil[v][0]), innerget(mid, r, lq, rq, innerchil[v][1]));
    }
 
 
    void upd(int l, int r, int id, int id2, ll val, int v){
        if(!inner[v])
            inner[v] = innernode++;
        //cout << "entering iiner update " << l << ' ' << r << ' ' << v << ' ' << inner[v] << ' ' << val << endl;
        if(r - l == 1){
            innerupdbase(0, m, id2, val, inner[v]);
            return;
        }
        int mid = (l + r) >> 1;
        if(id < mid){
            if(!chil[v][0])
                chil[v][0] = newnode++;
            upd(l, mid, id, id2, val, chil[v][0]);
        }
        else{
            if(!chil[v][1])
                chil[v][1] = newnode++;
            upd(mid, r, id, id2, val, chil[v][1]);
        }
        innerupdult(0, m, id2, inner[v], inner[chil[v][0]], inner[chil[v][1]]);
    }
 
    ll get(int l, int r, int lq, int rq, int llq, int rrq, int v){
        if(v == 0 || rq <= l || r <= lq)
            return 0;
        if(lq <= l && r <= rq){
            if(!inner[v])
                return 0;
            ll ret = innerget(0, m, llq, rrq, inner[v]);
            //cout << "here " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << ret << endl;
            return ret;
        }
        int mid = (l + r) >> 1;
        return gcd2(get(l, mid, lq, rq, llq, rrq, chil[v][0]), get(mid, r, lq, rq, llq, rrq, chil[v][1]));
    }
 
    inline void clear(int nn, int mm){
        n = nn;
        m = mm;
        for(int i = 0; i < newnode; i++)
            inner[i] = chil[i][0] = chil[i][1] = 0;
        for(int i = 0; i < innernode; i++)
            innerchil[i][0] = innerchil[i][1] = g[i] = 0;
        newnode = innernode = 2;
    }
}
 
int szx, szy, n, m;
int newnode = 2, innernode = 2, inner[maxnt];
int chil[maxnt][2], innerchil[maxnt][2];
ll g[maxnt];
vector <int> avx, avy;
map <pair<int, int>, ll> av;
set <pair<int, int>> avseg;
 
void innerupdbase(int l, int r, int id, ll val, int v){
    //cout << "inner upd with " << l << ' ' << r << ' ' << id << ' ' << val << ' ' << v << endl;
    if(r - l == 1){
        g[v] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if(id < mid){
        if(!innerchil[v][0])
            innerchil[v][0] = innernode++;
        innerupdbase(l, mid, id, val, innerchil[v][0]);
    }
    else{
        if(!innerchil[v][1])
            innerchil[v][1] = innernode++;
        innerupdbase(mid, r, id, val, innerchil[v][1]);
    }
    g[v] = gcd2(g[innerchil[v][0]], g[innerchil[v][1]]);
    //cout << "ok " << l << ' ' << r << ' ' << val << ' ' << v << ' ' << g[v] << ' ' << g[innerchil[v][1]] << ' ' << g[innerchil[v][0]] << endl;
}
 
void innerupdult(int l, int r, int id, int v1, int v2, int v3){
    g[v1] = gcd2(g[v2], g[v3]);
    if(r - l == 1)
        return;
    int mid = (l + r) >> 1;
    if(id < mid){
        if(!innerchil[v1][0])
            innerchil[v1][0] = innernode++;
        innerupdult(l, mid, id, innerchil[v1][0], innerchil[v2][0], innerchil[v3][0]);
    }
    else{
        if(!innerchil[v1][1])
            innerchil[v1][1] = innernode++;
        innerupdult(mid, r, id, innerchil[v1][1], innerchil[v2][1], innerchil[v3][1]);
    }
}
 
 
ll innerget(int l, int r, int lq, int rq, int v){
    if(v == 0 || rq <= l || r <= lq)
        return 0;
    if(lq <= l && r <= rq){
        //cout << "inner getting " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << g[v] << endl;
        return g[v];
    }
    int mid = (l + r) >> 1;
    return gcd2(innerget(l, mid, lq, rq, innerchil[v][0]), innerget(mid, r, lq, rq, innerchil[v][1]));
}
 
 
void upd(int l, int r, int id, int id2, ll val, int v){
    if(!inner[v])
        inner[v] = innernode++;
    //cout << "entering iiner update " << l << ' ' << r << ' ' << v << ' ' << inner[v] << ' ' << val << endl;
    if(r - l == 1){
        innerupdbase(0, m, id2, val, inner[v]);
        return;
    }
    int mid = (l + r) >> 1;
    if(id < mid){
        if(!chil[v][0])
            chil[v][0] = newnode++;
        upd(l, mid, id, id2, val, chil[v][0]);
    }
    else{
        if(!chil[v][1])
            chil[v][1] = newnode++;
        upd(mid, r, id, id2, val, chil[v][1]);
    }
    innerupdult(0, m, id2, inner[v], inner[chil[v][0]], inner[chil[v][1]]);
}
 
ll get(int l, int r, int lq, int rq, int llq, int rrq, int v){
    if(v == 0 || rq <= l || r <= lq)
        return 0;
    if(lq <= l && r <= rq){
        if(!inner[v])
            return 0;
        ll ret = innerget(0, m, llq, rrq, inner[v]);
        //cout << "here " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << ret << endl;
        return ret;
    }
    int mid = (l + r) >> 1;
    return gcd2(get(l, mid, lq, rq, llq, rrq, chil[v][0]), get(mid, r, lq, rq, llq, rrq, chil[v][1]));
}
 
void init(int R, int C) {
    n = R;
    m = C;
    /* ... */
}
 
 
inline void rebuild(){
    sort(all(avx));
    sort(all(avy));
    avx.resize(unique(all(avx)) - avx.begin());
    avy.resize(unique(all(avy)) - avy.begin());
    szx = avx.size();
    szy = avy.size();
 
    for(int i = 0; i < newnode; i++)
        inner[i] = chil[i][0] = chil[i][1] = 0;
    for(int i = 0; i < innernode; i++)
        innerchil[i][0] = innerchil[i][1] = g[i] = 0;
    newnode = innernode = 2;
    seg::clear(szx, szy);
    for(auto it = av.begin(); it != av.end(); it++){
        avseg.insert(it->fi);
        int ptx = lower_bound(avx.begin(), avx.begin() + szx, (it->fi).fi) - avx.begin();
        int pty = lower_bound(avy.begin(), avy.begin() + szy, (it->fi).se) - avy.begin();
        seg::upd(0, szx, ptx, pty, it->se, 1);
    }
}

int opt = 0;

void update(int x, int y, long long k) {
    opt++;
    if(newnode > 5e6 || innernode > 5e6)
        rebuild();
    if(avseg.find(mp(x, y)) != avseg.end()){
        av[{x, y}] = k;
        x = lower_bound(avx.begin(), avx.begin() + szx, x) - avx.begin();
        y = lower_bound(avy.begin(), avy.begin() + szy, y) - avy.begin();
        seg::upd(0, szx, x, y, k, 1);
        return;
    }
    upd(0, n, x, y, k, 1);
    av[{x, y}] = k;
    avx.pb(x);
    avy.pb(y);
}
 
long long calculate(int l, int d, int r, int u) {

    tt++;
 
    ll ans = get(0, n, l, r + 1, d, u + 1, 1);
    //if(tt == 129048)
    //    cerr << l << ' ' << r << ' ' << d << ' ' << u << endl;
    l = lower_bound(avx.begin(), avx.begin() + szx, l) - avx.begin();
    r = upper_bound(avx.begin(), avx.begin() + szx, r) - avx.begin();
    d = lower_bound(avy.begin(), avy.begin() + szy, d) - avy.begin();
    u = upper_bound(avy.begin(), avy.begin() + szy, u) - avy.begin();
    ans = gcd2(ans, seg::get(0, szx, l, r, d, u, 1));
    //if(tt == 129048)
    //    cerr << newnode << ' ' << innernode << ' ' << ans << ' ' << opt << ' ' << l << ' ' << r << ' ' << d << ' ' << u << endl;
    return ans;
}

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