Submission #590414

#	Time	Username	Problem	Language	Result	Execution time	Memory
590414		jeroenodb	Game (IOI13_game)	C++17	100 / 100	8183 ms	73324 KiB

game

#include "game.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
ll r,c;
ll ans=0;
struct node2 {
    ll pos=-1,len;
    ll g=0,lazy=0;
    node2 *l=NULL, *r = NULL;
    node2(ll n) : len(n) {}
    static ll total(node2* nd) {
        return nd?gcd(nd->g,nd->lazy):0LL;
    }
    void query(ll a, ll b) const {
        if(b<0 or a>=len) return;
        if(pos!=-1 and a<=pos and pos<=b) ans = gcd(ans,lazy);
        if(a<=0 and b>=len-1) {
            ans = gcd(ans,g);
            return;
        }
        ll mid = len/2;
        if(l) l->query(a,b);
        if(r) r->query(a-mid,b-mid);
    }
    void update(ll y, ll v) {
        if(y==pos or pos==-1) {
            pos = y;
            lazy=v;
            return;
        }
        ll mid = len/2;
        if(y<mid) {
            if(!l) l = new node2(mid);
            l->update(y,v);
        } else {
            if(!r) r = new node2(len-mid);
            r->update(y-mid,v);
        }
        g = gcd(total(l),total(r));
    }
};
struct node {
    node *l = NULL, *r = NULL;
    int len; // make it power of 2?
    node2 *sub = NULL;
    node(int n) : len(n) {}
    node() {}
    void query(int cc, int dd, int a,int b) const {
        if(dd<0 or cc>=len) return;
        int mid = len/2;
        if(cc<=0 and dd>=len-1) {
            if(sub) sub->query(a*::r,b*::r+::r-1);
            return;
        }
        if(l) l->query(cc,dd,a,b);
        if(r) r->query(cc-mid,dd-mid,a,b);
    }
    void update(int x, int y, ll v) {
        
        if(!sub) sub = new node2(c*::r);
        sub->update(y*::r + x,v);
        if(len==1) return;
        int mid = len/2;
        if(x<mid) {
            if(!l) l = new node(mid);
            l->update(x,y,v);
        } else {
            if(!r) r = new node(len-mid);
            r->update(x-mid,y,v);
        }
    }
} root;

vvi a;
void init(int R, int C) {
    r=R,c=C;
    // a.assign(R,vi(C));
    root = node(R);
}

vi queries;
void update(int P, int Q, long long K) {
    // cout << "1 " << P << ' ' << Q << ' ' << K << '\n';
    // a[P][Q]=K;
    root.update(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    
    ans=0;
    root.query(P,U,Q,V);
    // cout << "2 " << P << ' ' << Q << ' ' << U << ' ' << V << '\n';
    // ll bans=0;
    // for(int i=P;i<=U;++i) {
    //     for(int j=Q;j<=V;++j) {
    //         bans=gcd(bans,a[i][j]);
    //     }
    // }
    // if(ans!=bans) {
    //     exit(0);
    // }
    return ans;
}
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
template<class I> I rnd(I l,I r){return std::uniform_int_distribution<I>(l,r)(rng);}
#ifdef LOCALfg
int main() {
    while(true) {
        int R = rnd(2,4),C = rnd(2,4);
        cout << "TEST!\n";
        cout << R << ' '<< C << '\n';
        init(R,C);
        for(int i=0;i<6;++i) {
            if(rnd(0,1)==0) {
                update(rnd(0,R-1),rnd(0,C-1), rnd(0,50));
            } else {
                auto get = [&](int B) {
                    int l=rnd(0,B-1),r=rnd(0,B-1);
                    if(l>r) swap(l,r);
                    return pi{l,r};
                };
                auto [P,U] = get(R);
                auto [Q,V] = get(C);
                calculate(P,Q,U,V);
            }
        }
    }
}
#endif

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