Submission #1080827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080827		Gray	Game (IOI13_game)	C++17	63 / 100	1000 ms	256000 KiB

game

#include<bits/stdc++.h>
#include "game.h"
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
struct SegTree1D{
    struct Node{
        Node *left, *right;
        ll gcd;
        Node(){
            left=right=nullptr; gcd=0;
        }
        void update(ll tl, ll tr, ll i, ll x, map<ll, Node*> &leaves){
            if (tl==tr){
                gcd=x;
                leaves[tl]=this;
            }else{
                ll tm = (tl+tr)/2;
                if (i<=tm) {
                    if (!left) left=new Node();
                    left->update(tl, tm, i, x, leaves);
                }else{
                    if (!right) right=new Node();
                    right->update(tm+1, tr, i, x, leaves);
                }
                gcd=0;
                if(left) gcd=__gcd(left->gcd, gcd);
                if (right) gcd=__gcd(right->gcd, gcd);
            }
        }
        ll query(ll tl, ll tr, ll l, ll r){
            if (tl==l and tr==r){
                return gcd;
            }else if (l>r) return 0;
            else{
                ll tm = (tl+tr)/2;
                ll ret=0;
                if (left and l<=min(r, tm)) ret=__gcd(ret, left->query(tl, tm, l, min(r, tm)));
                if (right and max(l, tm+1)<=r) ret=__gcd(ret, right->query(tm+1, tr, max(l, tm+1), r));
                return ret;
            }
        }
    };
    map<ll, Node*> leaves;
    Node * root;
    ll rsz;
    SegTree1D(ll N){
        rsz=N;
        root=new Node();
    }
    void update(ll i, ll x){
        root->update(0, rsz-1, i, x, leaves);
    }
    ll query(ll l, ll r){
        return root->query(0, rsz-1, l, r);
    }
    ll getval(ll ind){
        if (!leaves.count(ind)) return 0;
        return leaves[ind]->gcd;
    }
};
struct SegTree2D{
    struct mNode{
        mNode *left, *right;
        SegTree1D *val;
        ll csz;
        mNode(ll _csz){
            csz=_csz;
            left=right=nullptr;
            val = new SegTree1D(csz);
        }
        void update(ll tl, ll tr, ll i, ll j, ll x){
            if (tl==tr){
                val->update(j, x);
            }else{
                ll tm = (tl+tr)/2;
                if (i<=tm){
                    if (!left) left=new mNode(csz);
                    left->update(tl, tm, i, j, x);
                }else{
                    if (!right) right=new mNode(csz);
                    right->update(tm+1, tr, i, j, x);
                }
                val->update(j, __gcd((left?left->val->getval(j):0), (right?right->val->getval(j):0)));
            }
        }
        ll query(ll li, ll ri, ll lj, ll rj, ll tl, ll tr){
            if (tl==li and tr==ri){
                return val->query(lj, rj);
            }else if (li>ri) return 0;
            else{
                ll ret=0;
                ll tm = (tl+tr)/2;
                if (left and li<=min(ri, tm)) ret=__gcd(ret, left->query(li, min(ri, tm), lj, rj, tl, tm));
                if (right and max(li, tm+1)<=ri) ret=__gcd(ret, right->query(max(li, tm+1), ri, lj, rj, tm+1, tr));
                return ret;
            }
        }
    };
    mNode * root;
    ll csz, rsz;
    void init(ll R, ll C){
        rsz=R; csz=C;
        root = new mNode(csz);
    }
    void update(ll i, ll j, ll x){
        root->update(0, rsz-1, i, j, x);
    }
    ll query(ll li, ll ri, ll lj, ll rj){
        return root->query(li, ri, lj, rj, 0, rsz-1);
    }
} DS;


void init(int R, int C) {
    DS.init(R, C);
}

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

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

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