Submission #553257

#	Time	Username	Problem	Language	Result	Execution time	Memory
553257		Jarif_Rahman	Game (IOI13_game)	C++17	80 / 100	3866 ms	95260 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;

const int lim1 = 22000*30, lim2 = 22000*30;

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

Node T1[lim1];
int cnt1 = 0;

Node* newNode(int X, int Y, ll x){
    T1[cnt1] = Node(X, Y, x);
    return &T1[cnt1++];
}

namespace Treap{
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    void upd_nd(Node *nd){
        if(!nd) return;
        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, int 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;
        }
    }

    bool search_upd(Node *nd, int 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;
        }
    }

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

    void update(Node *&root, int X, ll x){
        if(!search_upd(root, X, x)) insert(root, X, x);
    }

    ll get(Node* nd, int X){
        if(!nd) return 0;
        if(nd->X == X) return nd->x;
        if(nd->X > X) return get(nd->l, X);
        return get(nd->r, X);
    }

    ll get(Node *& rt, int a, int 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 Node2d{
    Node2d *l = nullptr, *r = nullptr;
    Node* tp = nullptr;
    Node2d(){}
};

Node2d T2[lim2];
int cnt2 = 0;

Node2d* newNode2d(){
    return &T2[cnt2++];
}

struct sparse_segtree2d{
    int n, m;
    Node2d* root;
    sparse_segtree2d(int _n, int _m){
        n = _n, m = _m;
        root = newNode2d();
    }

    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 = newNode2d();
                upd(nd->l, l, (l+r)/2, a, b, x);
            }
            else{
                if(!nd->r) nd->r = newNode2d();
                upd(nd->r, (l+r)/2+1, r, a, b, x);
            }
            ll s = 0;
            if(nd->l) s = __gcd(s, Treap::get(nd->l->tp, b));
            if(nd->r) s = __gcd(s, Treap::get(nd->r->tp, b));
            Treap::update(nd->tp, b, s);
        }
        else Treap::update(nd->tp, b, x);
    }
    void upd(int a, int b, ll x){
        upd(root, 0, n-1, a, b, x);
    }

    ll get(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 Treap::get(nd->tp, b1, b2);
        int md = (L+R)/2;
        ll rt = 0;
        if(nd->l) rt = __gcd(rt, get(nd->l, L, md, a1, b1, a2, b2));
        if(nd->r) rt = __gcd(rt, get(nd->r, md+1, R, a1, b1, a2, b2));
        return rt;
    }
    ll get(int a1, int b1, int a2, int b2){
        return get(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.get(P, Q, U, V);
}

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