Submission #330918

#	Time	Username	Problem	Language	Result	Execution time	Memory
330918		smax	Game (IOI13_game)	C++17	80 / 100	4857 ms	256004 KiB

game

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

// Source: https://github.com/kth-competitive-programming/kactl/blob/master/content/various/BumpAllocator.h

static char buf[450 << 20];
void* operator new(size_t s) {
    static size_t i = sizeof buf;
    assert(s < i);
    return (void*)&buf[i -= s];
}
void operator delete(void*) {}

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;
}

struct Node {
    long long ans;
    Node *l, *r;
    
    Node() : ans(0), l(NULL), r(NULL) {}
};

long long query(Node *p, int l, int r, int i, int j) {
    if (i > r || j < l || !p)
        return 0;
    if (i <= l && r <= j)
        return p->ans;
    int m = (l + r) / 2;
    return gcd2(query(p->l, l, m, i, j), query(p->r, m+1, r, i, j));
}

void update(Node *p, int l, int r, int idx, long long val) {
    if (l == r) {
        p->ans = val;
        return;
    }
    int m = (l + r) / 2;
    if (idx <= m) {
        if (!p->l) p->l = new Node();
        update(p->l, l, m, idx, val);
    } else {
        if (!p->r) p->r = new Node();
        update(p->r, m+1, r, idx, val);
    }
    p->ans = gcd2((p->l ? p->l->ans : 0), (p->r ? p->r->ans : 0));
}

struct Seg {
    Node *node;
    Seg *l, *r;
    
    Seg() : node(new Node()), l(NULL), r(NULL) {}
};

int n, _r;

long long query(Seg *p, int l, int r, int ix, int iy, int jx, int jy) {
    if (ix > r || jx < l || !p)
        return 0;
    if (ix <= l && r <= jx)
        return query(p->node, 0, n-1, iy, jy);
    int m = (l + r) / 2;
    return gcd2(query(p->l, l, m, ix, iy, jx, jy), query(p->r, m+1, r, ix, iy, jx, jy));
}
    
void update_y(Node *p, Node *pl, Node *pr, int l, int r, int y, long long val) {
    if (l != r) {
        int m = (l + r) / 2;
        if (y <= m) {
            if (!p->l) p->l = new Node();
            update_y(p->l, pl ? pl->l : NULL, pr ? pr->l : NULL, l, m, y, val);
        } else {
            if (!p->r) p->r = new Node();
            update_y(p->r, pl ? pl->r : NULL, pr ? pr->r : NULL, m+1, r, y, val);
        }
    }
    p->ans = gcd2((pl ? pl->ans : 0), (pr ? pr->ans : 0));
}

void update(Seg *p, int l, int r, int x, int y, long long val) {
    if (l == r) {
        update(p->node, 0, n-1, y, val);
        return;
    }
    int m = (l + r) / 2;
    if (x <= m) {
        if (!p->l) p->l = new Seg();
        update(p->l, l, m, x, y, val);
    } else {
        if (!p->r) p->r = new Seg();
        update(p->r, m+1, r, x, y, val);
    }
    update_y(p->node, p->l ? p->l->node : NULL, p->r ? p->r->node : NULL, 0, n-1, y, val);
}

Seg st;

void init(int R, int C) {
    n = C;
    _r = R;
}

void update(int P, int Q, long long K) {
    update(&st, 0, _r-1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query(&st, 0, _r-1, P, Q, U, V);
}

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