Submission #687923

#	Time	Username	Problem	Language	Result	Execution time	Memory
687923		vjudge1	Game (IOI13_game)	C++17	100 / 100	7295 ms	57228 KiB

game

#include <game.h>
#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second

using namespace std;
const int oo = 2e9;

struct node {
    node *l, *r;
    int wt, val, g;
    ii co;
    node (ii pos, int x)
    {
        l = r = 0;
        wt = rand();
        val = g = x;
        co = pos;
    }
};
#define nd node*

inline int gg(nd x) {return x ? x->g : 0;}
inline void upd(nd x) {x->g = __gcd(__gcd(gg(x->l), gg(x->r)), x->val);}

inline void merg(nd &x, nd l, nd r)
{
    if (!l || !r) return void(x=l?l:r);
    if (l->wt < r->wt) merg(r->l, l, r->l), x = r;
    else merg(l->r, l->r, r), x = l;
    upd(x);
}

inline void split(nd x, nd &l, nd &r, ii pos)
{
    if (!x) return void(l=r=0);
    if (x->co <= pos) split(x->r, x->r, r, pos), l = x;
    else split(x->l, l, x->l, pos), r = x;
    upd(x);
}

inline void ins(nd &x, ii pos, int val)
{
    node *a, *b;
    split(x, x, a, {pos.ff, pos.ss-1});
    split(a, a, b, pos);
    merg(x, x, new node(pos, val));
//    merg(a, a, b);
    merg(x, x, b);
}

inline int qry1(nd &x, int l, int r)
{
    node *a, *b;
    split(x, x, a, {l-1, oo});
    split(a, a, b, {r, oo});
    int ans = gg(a);
    merg(a, a, b);
    merg(x, x, a);
    return ans;
}

struct Node {
    Node *l, *r;
    nd st;
    Node() {
        l = r = 0;
        st = 0;
    }
};
Node *root = new Node();

inline void upd(Node *&cur, int lx, int rx, int x, int y, int val)
{
    if (!cur) cur = new Node();
    ins(cur->st, {y, x}, val);
    if (lx == rx) return;
    int m = (lx + rx) >> 1;
    if (x <= m) upd(cur->l, lx, m, x, y, val);
    else upd(cur->r, m+1, rx, x, y, val);
}

inline int qry(Node *&x, int lb, int rb, int lx, int rx, int ly, int ry)
{
    if (lx > rx || !x) return 0;
    else if (lb == lx && rb == rx) return qry1(x->st, ly, ry);
    int m = (lb + rb) >> 1;
    return __gcd(qry(x->l, lb, m, lx, min(rx, m), ly, ry),
                 qry(x->r, m+1, rb, max(lx, m+1), rx, ly, ry));
}

int l1, r1;
void init(signed r, signed c) {
    l1 = 0, r1 = r - 1;
}

void update(signed x, signed y, int k) {
    upd(root, l1, r1, x, y, k);
}

int calculate(signed x, signed y, signed u, signed v) {
    return qry(root, l1, r1, x, u, y, v);
}

//signed main()
//{
//    ios_base::sync_with_stdio(false);
//    cin.tie(nullptr); cout.tie(nullptr);
//    init(2, 3);
//    update(0, 0, 20);
//    update(0, 2, 15);
//    update(1, 1, 12);
//    cerr<<calculate(0, 0, 0, 2)<<"\n";
//    cerr<<calculate(0, 0, 1, 1)<<"\n";
//    update(0, 1, 6);
//    update(1, 1, 14);
//    cerr<<calculate(0, 0, 0, 2)<<"\n";
//    cerr<<calculate(0, 0, 1, 1)<<"\n";
//}

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