Submission #1068447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068447		GrindMachine	Game (IOI13_game)	C++17	100 / 100	6185 ms	141996 KiB

game

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

already knew the solution idea (dynamic segtree with a treap in each node)

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "game.h"

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node{
    node *l = nullptr, *r = nullptr;
    int siz = 0;
    unsigned int prior = 0;
    bool flip = 0;
    pii p = {0,0}, mxp = {0,0};
    ll val = 0, g = 0;

    node(int i, int j, ll v){
        l = r = nullptr;
        siz = 1;
        prior = rng();
        flip = 0;
        p = mxp = {i,j};
        val = v, g = v;
    }
 
    void recalc(){
        siz = 1, mxp = p, g = val;
        if(l) siz += l->siz, amax(mxp,l->mxp), g = gcd(g,l->g);
        if(r) siz += r->siz, amax(mxp,r->mxp), g = gcd(g,r->g);
    }

    void prop(){
        if(!flip) return;
        swap(l,r);
        if(l) l->flip ^= 1;
        if(r) r->flip ^= 1;
        flip = 0;
    }
 
    ~node(){
        delete l;
        delete r;
        l = r = nullptr;
    }
};
 
node* merge(node* u, node* v){
    if(u) u->prop();
    if(v) v->prop();
 
    if(u == nullptr) return v;
    if(v == nullptr) return u;
 
    if(u->prior > v->prior){
        // v goes to u's right subtree
        u->r = merge(u->r,v);
        u->recalc();
        return u;
    }
    else{
        // u goes to v's left subtree
        v->l = merge(u,v->l);
        v->recalc();
        return v;
    }
}

pair<node*,node*> split(node* u, int k){
    if(!u) return {nullptr,nullptr};
 
    u->prop();
 
    if(k == 0) return {nullptr,u};
    if(k == u->siz) return {u,nullptr};
 
    int pos = 1;
    if(u->l) pos += u->l->siz;
 
    if(k < pos){
        // required pos lies in the left subtree
        // root belongs to the right subtree
        auto p = split(u->l,k);
        u->l = p.ss;
        u->recalc();
        return {p.ff,u};
    }
    else{
        // required pos lies in the right subtree
        // root belongs to the left subtree
        auto p = split(u->r,k-pos);
        u->r = p.ff;
        u->recalc();
        return {u,p.ss};
    }
}

int ub(node* u, pii i){
    // first ind s.t pos > i (inds start from 1)
    if(u->l and u->l->mxp > i){
        return ub(u->l,i);
    }

    int add = (u->l?u->l->siz:0);

    if(u->p > i){
        return add+1;
    }

    if(u->r){
        return ub(u->r,i)+add+1;
    }
    else{
        return add+2;
    }
}

vector<node*> split_many(node* treap, vector<int> cuts){
    vector<node*> parts;
    rev(i,sz(cuts)-1,0){
        auto p = split(treap,cuts[i]);
        treap = p.ff;
        parts.pb(p.ss);
    }
 
    parts.pb(treap);
    reverse(all(parts));
    return parts;
}
 
node* merge_many(vector<node*> parts){
    node* treap = nullptr;
    trav(part,parts){
        treap = merge(treap,part);
    }
    return treap;
}

struct dynamic_treap{
    node* treap = new node(0,0,0);
    
    void pupd(int i, int j, ll v){
        pii px = {i,j};
        int pos = ub(treap,px);
        auto parts = split_many(treap,{pos-1});

        if(parts[0] and parts[0]->mxp == px){
            auto new_parts = split_many(parts[0],{parts[0]->siz-1});
            parts[0] = new_parts[0];
        }

        parts.insert(parts.begin()+1,new node(i,j,v));    
        treap = merge_many(parts);
    }   

    ll query(int l, int r){
        l = ub(treap,{l,-1});
        r = ub(treap,{r+1,-1})-1;
        if(l > r) return 0ll;
        auto parts = split_many(treap,{l-1,r});
        ll res = parts[1]->g;
        treap = merge_many(parts);
        return res;
    }
};

struct dynamic_segtree{
    struct node{
        node *l = nullptr, *r = nullptr;
        dynamic_treap treap;
        node(){

        }
    };

    node* root;
    int n;

    dynamic_segtree(){

    }

    dynamic_segtree(int n_){
        root = new node();
        n = n_;
    }

    void pupd(node* &u, int lx, int rx, int i, int j, ll v){
        u->treap.pupd(j,i,v);
        if(rx-lx == 1) return;

        int mid = (lx+rx) >> 1;

        if(!u->l) u->l = new node();
        if(!u->r) u->r = new node();

        if(i < mid){
            pupd(u->l,lx,mid,i,j,v);
        }
        else{
            pupd(u->r,mid,rx,i,j,v);
        }
    }

    void pupd(int i, int j, ll v){
        pupd(root,0,n,i,j,v);
    }

    ll query(node* u, int lx, int rx, int l, int r, int x, int y){
        if(!u) return 0;
        if(lx >= r or rx <= l) return 0;
        if(lx >= l and rx <= r) return u->treap.query(x,y);
        
        int mid = (lx+rx) >> 1;
        return gcd(query(u->l,lx,mid,l,r,x,y),query(u->r,mid,rx,l,r,x,y));
    }

    ll query(int l, int r, int x, int y){
        return query(root,0,n,l,r+1,x,y);
    }
};

dynamic_segtree st;

void init(int n, int m) {
    st = dynamic_segtree(n);
}

void update(int i, int j, long long v) {
    st.pupd(i,j,v);
}

long long calculate(int l1, int l2, int r1, int r2) {
    return st.query(l1,r1,l2,r2);
}

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