Submission #1195216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195216		byunjaewoo	Game (IOI13_game)	C++20	80 / 100	2866 ms	240072 KiB

game

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

ll gcd__(ll a, ll b) {
    return b?gcd__(b, a%b):a;
}

int p, q;
struct Node {
    int l, r; ll val;
    Node() {l=r=-1, val=0;}
}buf[14500000];

const int S=1<<30;
class seg2d {
public:
    seg2d() { root=q++; }
    void update(int x, int y, ll v) { update(root, 0, S-1, x, y, v); }
    ll query(int s, int e, int l, int r) { return query(root, 0, S-1, s, e, l, r); }
private:
    class seg1d {
    public:
        int root, l, r;
        seg1d() { root=l=r=-1; }
        void update(int k, ll v) {
            if(root<0) root=p++;
            update(root, 0, S-1, k, v);
        }
        void merge(int k, int v1, int v2) {
            if(root<0) root=p++;
            merge(root, v1, v2, 0, S-1, k);
        }
        ll query(int l, int r) {
            if(root<0) root=p++;
            return query(root, 0, S-1, l, r);
        }
    private:
        void update(int curr, int s, int e, int k, ll v) {
            if(s==e) {
                buf[curr].val=v; return;
            }
            int m=(s+e)/2;
            if(k<=m) {
                if(buf[curr].l<0) buf[curr].l=p++;
                update(buf[curr].l, s, m, k, v);
                if(buf[curr].r>=0) buf[curr].val=gcd__(buf[buf[curr].l].val, buf[buf[curr].r].val);
                else buf[curr].val=buf[buf[curr].l].val;
            }
            else {
                if(buf[curr].r<0) buf[curr].r=p++;
                update(buf[curr].r, m+1, e, k, v);
                if(buf[curr].l>=0) buf[curr].val=gcd__(buf[buf[curr].l].val, buf[buf[curr].r].val);
                else buf[curr].val=buf[buf[curr].r].val;
            }
        }
        void merge(int curr, int curr1, int curr2, int s, int e, int k) {
            buf[curr].val=gcd__((curr1>=0)?buf[curr1].val:0, (curr2>=0)?buf[curr2].val:0);
            if(s==e) return;
            int m=(s+e)/2;
            if(k<=m) {
                if(buf[curr].l<0) buf[curr].l=p++;
                merge(buf[curr].l, (curr1>=0)?buf[curr1].l:-1, (curr2>=0)?buf[curr2].l:-1, s, m, k);
            }
            else {
                if(buf[curr].r<0) buf[curr].r=p++;
                merge(buf[curr].r, (curr1>=0)?buf[curr1].r:-1, (curr2>=0)?buf[curr2].r:-1, m+1, e, k);
            }
        }
        ll query(int curr, int s, int e, int l, int r) {
            if(curr<0 || s>r || l>e) return 0;
            if(l<=s && e<=r) return buf[curr].val;
            int m=(s+e)/2;
            return gcd__(query(buf[curr].l, s, m, l, r), query(buf[curr].r, m+1, e, l, r));
        }
    }tree[700000];
    int root;
    void update(int curr, int s, int e, int x, int y, ll v) {
        if(s==e) {
            tree[curr].update(y, v);
            return;
        }
        int m=(s+e)/2;
        if(x<=m) {
            if(tree[curr].l<0) tree[curr].l=q++;
            update(tree[curr].l, s, m, x, y, v);
        }
        else {
            if(tree[curr].r<0) tree[curr].r=q++;
            update(tree[curr].r, m+1, e, x, y, v);
        }
        tree[curr].merge(y, (tree[curr].l>=0)?tree[tree[curr].l].root:-1, (tree[curr].r>=0)?tree[tree[curr].r].root:-1);
    }
    ll query(int curr, int s, int e, int l, int r, int ll, int rr) {
        if(curr<0 || s>r || l>e) return 0;
        if(l<=s && e<=r) return tree[curr].query(ll, rr);
        int m=(s+e)/2;
        return gcd__(query(tree[curr].l, s, m, l, r, ll, rr), query(tree[curr].r, m+1, e, l, r, ll, rr));
    }
}T;

void init(int R, int C) {}

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

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

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