Submission #1030637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030637		tolbi	Game (IOI13_game)	C++17	100 / 100	3708 ms	67532 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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;
}
mt19937_64 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
struct Treap{
    struct Node{
        Node *lnode, *rnode;
        ll val, gg, h;
        int pos;
        Node(int pos, ll x):val(x),gg(x),h(ayahya()),pos(pos),lnode(nullptr),rnode(nullptr){}
    } *root;
    Treap():root(nullptr){}
    void upd(Node* nd){
        nd->gg=nd->val;
        if (nd->lnode) nd->gg=gcd2(nd->lnode->gg,nd->gg);
        if (nd->rnode) nd->gg=gcd2(nd->rnode->gg,nd->gg);
    }
    Node* merge(Node* a, Node* b){
        if (!a || !b) return (a?a:b);
        if (a->h > b->h) return a->rnode = merge(a->rnode,b),upd(a),a;
        return b->lnode = merge(a,b->lnode),upd(b),b;
    }
    pair<Node*, Node*> split(Node* node, int x){
        if (!node) return {nullptr,nullptr};
        if (node->pos>=x){
            pair<Node*, Node*> spl = split(node->lnode,x);
            node->lnode=spl.second;
            upd(node);
            return {spl.first,node};
        }
        pair<Node*, Node*> spl = split(node->rnode,x);
        node->rnode=spl.first;
        upd(node);
        return {node,spl.second};
    }
    void update(int x, ll val){
        if (root==nullptr){
            return root = new Node(x,val), void(23);
        }
        Node* nd = root;
        while (nd){
            if (nd->pos==x) break;
            if (nd->pos>x) nd=nd->lnode;
            else nd=nd->rnode;
        }
        if (nd==nullptr){
            Node* nnode = new Node(x,val);
            pair<Node*, Node*> spl = split(root,x);
            root=merge(spl.first,nnode);
            root=merge(root,spl.second);
        }
        else {
            vector<Node*> backtrack;
            nd->val=val;
            upd(nd);
            nd = root;
            while (nd->pos!=x){
                backtrack.push_back(nd);
                if (nd->pos>x) nd=nd->lnode;
                else nd=nd->rnode;
            }
            while (backtrack.size()){
                upd(backtrack.back());
                backtrack.pop_back();
            }
        }
    }
    ll queri(int x){
        Node* nd = root;
        while (nd!=nullptr){
            if (nd->pos==x) return nd->val;
            if (nd->pos>x) nd=nd->lnode;
            else nd=nd->rnode;
        }
        return 0;
    }
    ll query(int l, int r){
        pair<Node*, Node*> spl = split(root, l);
        pair<Node*, Node*> spl2 = split(spl.second, r+1);
        ll ret = 0;
        if (spl2.first) ret = spl2.first->gg;
        root = merge(spl2.first,spl2.second);
        root = merge(spl.first,root);
        return ret;
    }
};
constexpr int MAXN = 1000000000;
struct SegTree{
    struct Node{
        Node *lnode, *rnode;
        Treap tr;
        Node():lnode(nullptr),rnode(nullptr){}
    } *root;
    SegTree():root(new Node){}
    void update(int x, int y, ll val, int l = 0, int r = MAXN, Node* nd = nullptr){
        if (l==0 && r==MAXN) nd=root;
        if (l==r){
            return nd->tr.update(y,val);
        }
        int mid = l+(r-l)/2;
        if (mid>=x){
            if (nd->lnode==nullptr) nd->lnode=new Node;
            update(x,y,val,l,mid,nd->lnode);
        }
        else {
            if (nd->rnode==nullptr) nd->rnode=new Node;
            update(x,y,val,mid+1,r,nd->rnode);
        }
        ll ret = 0;
        if (nd->lnode) ret=nd->lnode->tr.queri(y);
        if (nd->rnode) ret=gcd2(nd->rnode->tr.queri(y),ret);
        nd->tr.update(y,ret);
    }
    ll query(int tl, int tr, int a, int b, int l = 0, int r = MAXN, Node* node = nullptr){
        if (l==0 && r==MAXN) node=root;
        if (l>=tl && r<=tr) return node->tr.query(a,b);
        if (l>tr || r<tl) return 0;
        int mid = l+(r-l)/2;
        ll ret = 0;
        if (node->lnode && mid>=tl) ret=gcd2(ret,query(tl,tr,a,b,l,mid,node->lnode));
        if (node->rnode && mid<tr) ret=gcd2(ret,query(tl,tr,a,b,mid+1,r,node->rnode));
        return ret;
    }
} segtree;
void init(int R, int C) {
        //23 severim
}

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

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

Compilation message (stderr)

game.cpp: In constructor 'Treap::Node::Node(int, ll)':
game.cpp:19:13: warning: 'Treap::Node::pos' will be initialized after [-Wreorder]
   19 |         int pos;
      |             ^~~
game.cpp:17:15: warning:   'Treap::Node* Treap::Node::lnode' [-Wreorder]
   17 |         Node *lnode, *rnode;
      |               ^~~~~
game.cpp:20:9: warning:   when initialized here [-Wreorder]
   20 |         Node(int pos, ll x):val(x),gg(x),h(ayahya()),pos(pos),lnode(nullptr),rnode(nullptr){}
      |         ^~~~

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