Submission #1090810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090810		vjudge1	Game (IOI13_game)	C++17	100 / 100	2207 ms	73492 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll gcd(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Node {
    ll pos, key, mn, mx;
    ll val, g;
    Node *l, *r;

    Node(int posi, ll vali) {
        l = r = nullptr;
        key = rng();
        mn = mx = pos = posi;
        val = g = vali;
    }

    void update() {
        g = val;
        if(l) g = gcd(g, l->g);
        if(r) g = gcd(g, r->g);
        mn = (l ? l->mn : mn);
        mx = (r ? r->mx : mx);
    }
};

struct Treap {
    Node *root;

    Treap() { root = nullptr; }

    void split(Node *u, int x, Node *&l, Node *&r) {
        if(u == nullptr) {
            l = r = nullptr;
            return ;
        }

        if(u->pos < x) {
            split(u->r, x, l, r);
            u->r = l;
            l = u;
        } else {
            split(u->l, x, l, r);
            u->l = r;
            r = u;
        }

        u->update();
    }

    Node* merge(Node *l, Node *r) {
        if(!l || !r) return (l ? l : r);
        if(l->key < r->key) {
            l->r = merge(l->r, r);
            l->update();
            return l;
        } else {
            r->l = merge(l, r->l);
            r->update();
            return r;
        }
    }

    bool find(int id) {
        Node *u = root;
        while(u != nullptr) {
            if(u->pos == id) return 1;
            if(u->pos > id) {
                if(u->l == nullptr) return 0;
                u = u->l;
            }
            if(u->pos < id) {
                if(u->r == nullptr) return 0;
                u = u->r;
            }
        }
        return 0;
    }

    void update(Node *u, int p, ll v) {
        if(u->pos == p) {
            u->val = v;
            u->update();
            return ;
        }
        if(u->pos > p) update(u->l, p, v);
        else update(u->r, p, v);
        u->update();
    }

    void insert(int p, ll v) {
        if(find(p)) {
            update(root, p, v);
            return ;
        }
        Node *l, *r;
        split(root, p, l, r);
        root = merge(merge(l, new Node(p, v)), r);
    }

    ll query(Node *u, int tl, int tr) {
        if(u->mx < tl || tr < u->mn) return 0;
        if(tl <= u->mn && u->mx <= tr) return u->g;
        ll ans = (tl <= u->pos && u->pos <= tr ? u->val : 0);
        if(u->l) ans = gcd(ans, query(u->l, tl, tr));
        if(u->r) ans = gcd(ans, query(u->r, tl, tr));
        return ans;
    }

    ll query(int tl, int tr) { return (root ? query(root, tl, tr) : 0); }
};

struct SegTree {
    SegTree *l, *r;
    Treap t;
    int L, R;

    SegTree() { l = r = nullptr; }
    SegTree(int a, int b) : L(a), R(b), l(nullptr), r(nullptr) {}

    int tm() { return (L + R) / 2; }
    void add_l() { if(!l) l = new SegTree(L, tm()); }
    void add_r() { if(!r) r = new SegTree(tm()+1, R); }

    void merge(int p) {
        ll ans = 0;
        if(l) ans = gcd(ans, l->t.query(p, p));
        if(r) ans = gcd(ans, r->t.query(p, p));
        t.insert(p, ans);
    }

    void update(int x, int y, ll val) {
        if(x < L || R < x) return ;
        if(L == R) {
            t.insert(y, val);
            return ;
        }

        if(x <= tm()) {
            add_l();
            l->update(x, y, val);
        } else {
            add_r();
            r->update(x, y, val);
        }
        merge(y);
    }

    ll query(int x1, int x2, int y1, int y2) {
        if(x2 < L || R < x1) return 0;
        if(x1 <= L && R <= x2) return t.query(y1, y2);

        ll ans = 0;
        if(l) ans = gcd(ans, l->query(x1, x2, y1, y2));
        if(r) ans = gcd(ans, r->query(x1, x2, y1, y2));
        return ans;
    }
};

SegTree tree;

void init(int R, int C) {
    tree = SegTree(0, R-1);
}

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

ll calculate(int P, int Q, int U, int V) {
    return tree.query(P, U, Q, V);
}

Compilation message (stderr)

game.cpp: In constructor 'SegTree::SegTree(int, int)':
game.cpp:128:12: warning: 'SegTree::R' will be initialized after [-Wreorder]
  128 |     int L, R;
      |            ^
game.cpp:126:14: warning:   'SegTree* SegTree::l' [-Wreorder]
  126 |     SegTree *l, *r;
      |              ^
game.cpp:131:5: warning:   when initialized here [-Wreorder]
  131 |     SegTree(int a, int b) : L(a), R(b), l(nullptr), r(nullptr) {}
      |     ^~~~~~~

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