Submission #566479

#	Time	Username	Problem	Language	Result	Execution time	Memory
566479		Mazaalai	Game (IOI13_game)	C++17	63 / 100	1505 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e9+5;

int n, m;
ll gcd(ll a, ll b) {
    if (a == 0) return b;
    return gcd(b%a, a);
}
struct Node {
    ll val;
    Node *l, *r;
    Node() {
        val = 0;
        l = r = NULL;
    }
    void addSide() {
        if (l == NULL) {
            l = new Node();
            r = new Node();
        }
    }
};
struct SegTree {
    Node *tree;
    SegTree *l, *r;
    SegTree() {
        tree = new Node();
        l = r = NULL;
    }
    void addSide() {
        if (l == NULL) {
            l = new SegTree();
            r = new SegTree();
        }
    }
    void update(int l, int r, int id, ll val, Node *head) {
        if (l == r) {
            head->val = val;
            return;
        }
        int mid = (l+r)>>1;
        // head->addSide();
        if (id <= mid && !head->l) head->l = new Node();
        else if (mid < id && !head->r) head->r = new Node();

        if (id <= mid) update(l, mid, id, val, head->l);
        else update(mid+1, r, id, val, head->r);

        head->val = gcd((head->l ? head->l->val : 0ll), (head->r ? head->r->val : 0ll));
    }
    ll query(int l, int r, int L, int R, Node *head) {
        if (l > R || L > r || !head) return 0;
        if (L <= l && r <= R) return head->val;
        int mid = (l+r)>>1;
        return gcd(
            query(l, mid, L, R, head->l),
            query(mid+1, r, L, R, head->r)
        );
    }
    void update1D(int pos, ll val) {
        update(1, m, pos, val, tree);
    }
    ll query1D(int l, int r) {
        return query(1, m, l, r, tree);
    }
    ll query1D(int l) {
        return query(1, m, l, l, tree);
    }
} *root;

void update2D(int l, int r, int a, int b, ll val, SegTree *head) {
    if (l == r) {
        head->update1D(b, val);
        return;
    }
    int mid = (l+r)>>1;
    // head->addSide();
    if (a <= mid && !head->l) head->l = new SegTree();
    else if (mid < a && !head->r) head->r = new SegTree();
    if (a <= mid) update2D(l, mid, a, b, val, head->l);
    else update2D(mid+1, r, a, b, val, head->r);
    head->update1D(
        b,
        gcd(
            (head->l ? head->l->query1D(b) : 0),
            (head->r ? head->r->query1D(b) : 0)
        )
    );
}
ll query2D(int l, int r, int l1, int r1, int l2, int r2, SegTree *head) {
    if (l1 > r || l > r1 || !head) return 0;
    if (l1 <= l && r <= r1) return head->query1D(l2, r2);
    int mid = (l+r)>>1;
    return gcd(
        query2D(l, mid, l1, r1, l2, r2, head->l),
        query2D(mid+1, r, l1, r1, l2, r2, head->r)
    );
}

void init(int _n, int _m) {
    n = _n;
    m = _m;
    root = new SegTree();

}

void update(int a, int b, ll val) {
    update2D(1, n, a+1, b+1, val, root);
}
ll calculate(int l1, int l2, int r1, int r2) {
    return query2D(1, n, l1+1, r1+1, l2+1, r2+1, root);
}

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