Submission #256905

#	Time	Username	Problem	Language	Result	Execution time	Memory
256905		Falcon	Game (IOI13_game)	C++14	100 / 100	8393 ms	57080 KiB

game

#pragma GCC optimize("O2")

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

#ifdef DEBUG
    #include "debug.hpp"
#endif

using namespace std;

#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
    #define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);}
    #define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0;}
#else
    #define debug(x...)
    #define light_debug(x) 
#endif

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> uid(1, 1 << 29);

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

class treap{
    struct node{
        int i, p;
        ll v, g;
        node* l; node* r;

        node(int _i, ll _v){
            i = _i, v = _v, g = _v;
            l = r = 0;
            p = uid(rng);
        }

    };

    using pnode = node*;

    pnode root = 0;

    inline ll get_gcd(pnode t){
        return t ? t->g : 0;
    }

    inline void pull(pnode t){
        if(t) t->g = gcd2(gcd2(get_gcd(t->l), get_gcd(t->r)), t->v);
    }

    void split(pnode t, pnode& l, pnode& r, int i){
        if(!t)
            l = r = 0;
        else if(t->i <= i)
            split(t->r, t->r, r, i), l = t;
        else
            split(t->l, l, t->l, i), r = t;
        pull(t);
    }

    void merge(pnode& t, pnode l, pnode r){
        if(!l || !r)
            t = l ? l : r;
        else if(l->p > r->p)
            merge(l->r, l->r, r), t = l;
        else
            merge(r->l, l, r->l), t = r;
        pull(t);
    }

public:
    void update(int i, ll v){
        pnode l, m, r;
        split(root, m, r, i);
        split(m, l, m, i - 1);
        m = new node(i, v);
        merge(root, l, m);
        merge(root, root, r);
    }

    ll query(int s, int e){
        pnode l, m, r;
        split(root, l, m, s - 1);
        split(m, m, r, e);
        ll g = get_gcd(m);
        merge(root, l, m);
        merge(root, root, r);
        return g;
    }
};


class segtree{
    struct node{
        treap trp;
        node *l = 0; node* r = 0;
    };

    using pnode = node*;

    int R, C;  
    pnode root = 0;
    
    ll query(pnode& t, int s, int e, int p, int q, int u, int v){
        if(p > e || u < s || !t)
            return 0;
        if(p <= s && e <= u)
            return t->trp.query(q, v);
        return gcd2(query(t->l, s, (s + e) >> 1, p, q, u, v), query(t->r, (s + e + 2) >> 1, e, p, q, u, v));
    }

    void update(pnode& t, int s, int e, int p, int q, ll v){
        if(p < s || p > e)
            return;
        if(!t)
            t = new node();
        if(s == e)
            t->trp.update(q, v);
        else{
            update(t->l, s, (s + e) >> 1, p, q, v), update(t->r, (s + e + 2) >> 1, e, p, q, v);
            ll lv = query(t->l, s, (s + e) >> 1, 0, q, R - 1, q);
            ll rv = query(t->r, s, (s + e) >> 1, 0, q, R - 1, q);
            t->trp.update(q, gcd2(lv, rv));
        }
    }

    

public:    
    segtree(int _R = 0, int _C = 0){
        R = _R, C = _C;
    }

    inline void update(int p, int q, ll v){
        update(root, 0, R - 1, p, q, v);
    }   

    inline ll query(int p, int q, int u, int v){
        return query(root, 0, R - 1, p, q, u, v);
    }
};

segtree seg;

void init(int R, int C) {
    seg = segtree(R);
}

void update(int P, int Q, long long K) {
    seg.update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return seg.query(P, Q, U, V);
}

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: 20 / 20