Submission #553246

#	Time	Username	Problem	Language	Result	Execution time	Memory
553246		Jarif_Rahman	Game (IOI13_game)	C++17	63 / 100	3802 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

struct Treap{
    struct Node{
        Node *l = nullptr, *r = nullptr;
        ll X, Y;
        int size = 0;
        ll x, s;
        Node(ll _X, ll _Y, ll _x){
            X = _X, Y = _Y, x = _x, s = x;
        }
    };

    mt19937 rng;
    Node* rt = nullptr;

    Treap(){
        rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
    }

    int size(Node *nd){ return nd?nd->size:0; }
    int size(){ return size(rt); }
    void upd_nd(Node *nd){
        if(!nd) return;
        nd->size = size(nd->l)+size(nd->r)+1;
        nd->s = nd->x;
        if(nd->l) nd->s = __gcd(nd->s, nd->l->s);
        if(nd->r) nd->s = __gcd(nd->s, nd->r->s);
    }

    pair<Node*, Node*> split(Node* root, ll X){
        if(!root) return {nullptr, nullptr};
        if(root->X <= X){
            auto [L, R] = split(root->r, X);
            root->r = L;
            upd_nd(root);
            return {root, R};
        }
        else{
            auto [L, R] = split(root->l, X);
            root->l = R;
            upd_nd(root);
            return {L, root};
        }
    }

    Node* merge(Node* l, Node* r){
        if(!l) return r;
        if(!r) return l;
        if(l->Y >= r->Y){
            l->r = merge(l->r, r);
            upd_nd(l);
            return l;
        }
        else{
            r->l = merge(l, r->l);
            upd_nd(r);
            return r;
        }
    }

    Node* search(Node* nd, ll X){
        if(!nd) return nullptr;
        if(nd->X == X) return nd;
        if(nd->X > X) return search(nd->l, X);
        return search(nd->r, X);
    }
    Node* search(ll X){
        return search(rt, X);
    }

    bool search_upd(Node *nd, ll X, ll x){
        if(!nd) return 0;
        if(nd->X == X){
            nd->x = x;
            upd_nd(nd);
            return 1;
        }
        if(nd->X > X){
            if(search_upd(nd->l, X, x)){
                upd_nd(nd);
                return 1;
            }
            return 0;
        }
        else{
            if(search_upd(nd->r, X, x)){
                upd_nd(nd);
                return 1;
            }
            return 0;
        }
    }
    bool search_upd(ll X, ll x){
        return search_upd(rt, X, x);
    }

    void insert(ll X, ll x){
        auto [L, R] = split(rt, X);
        Node* nd = new Node(X, uniform_int_distribution(INT_MIN, INT_MAX)(rng), x);
        auto _rt = merge(L, nd);
        _rt = merge(_rt, R);
        rt = _rt;
    }

    void update(ll X, ll x){
        if(!search_upd(X, x)) insert(X, x);
    }

    ll get(ll a, ll b){
        auto [A, D] = split(rt, a-1);
        auto [B, C] = split(D, b);
        ll ret = B?B->s:0;
        auto _rt = merge(A, B);
        _rt = merge(_rt, C);
        rt = _rt;
        return ret;
    }
};

struct sparse_segtree2d{
    struct Node2d{
        Node2d *l, *r;
        Treap sm;
        Node2d(){}
        Node2d(int m){
            l  = nullptr, r = nullptr;
        }
    };
    int n, m;
    Node2d* root;
    sparse_segtree2d(int _n, int _m){
        n = _n, m = _m;
        root = new Node2d();
    }

    void upd(Node2d *nd, int l, int r, int a, int b, ll x){
        if(l != r){
            if(a <= (l+r)/2){
                if(!nd->l) nd->l = new Node2d();
                upd(nd->l, l, (l+r)/2, a, b, x);
            }
            else{
                if(!nd->r) nd->r = new Node2d();
                upd(nd->r, (l+r)/2+1, r, a, b, x);
            }
            ll sm = 0;
            if(nd->l) sm = __gcd(sm, nd->l->sm.get(b, b));
            if(nd->r) sm = __gcd(sm, nd->r->sm.get(b, b));
            nd->sm.update(b, sm);
        }
        else nd->sm.update(b, x);
    }
    void upd(int a, int b, ll x){
        upd(root, 0, n-1, a, b, x);
    }

    ll sum(Node2d* nd, int L, int R, int a1, int b1, int a2, int b2){
        if(L > a2 || R < a1) return 0;
        if(L >= a1 && R <= a2) return nd->sm.get(b1, b2);
        int md = (L+R)/2;
        ll rt = 0;
        if(nd->l) rt = __gcd(rt, sum(nd->l, L, md, a1, b1, a2, b2));
        if(nd->r) rt = __gcd(rt, sum(nd->r, md+1, R, a1, b1, a2, b2));
        return rt;
    }
    ll sum(int a1, int b1, int a2, int b2){
        return sum(root, 0, n-1, a1, b1, a2, b2);
    }
};

sparse_segtree2d sp(0, 0);

void init(int R, int C){
    sp = sparse_segtree2d(R, C);
}

void update(int P, int Q, ll K){
    sp.upd(P, Q, K);
}

ll calculate(int P, int Q, int U, int V){
    return sp.sum(P, Q, U, V);
}

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