Submission #254464

#	Time	Username	Problem	Language	Result	Execution time	Memory
254464		thecodingwizard	Krave (COI14_krave)	C++11	100 / 100	1139 ms	155384 KiB

krave

#include <bits/stdc++.h>

using namespace std;

#define maxn 100000
#define ii pair<int, int>
#define f first
#define s second

set<int> vert[4*maxn], horiz[4*maxn];

ii qry(int p, int i, int j, int k, int l, set<int> s[]) {
    ii ans = make_pair(*(--s[p].lower_bound(l)), *s[p].lower_bound(l));

    if (i != j) {
        int mid = (i+j)/2;
        ii a2;
        if (mid >= k) {
            a2 = qry((p << 1), i, mid, k, l, s);
        } else {
            a2 = qry(2*p+1, mid+1, j, k, l, s);
        }
        ans.f = max(ans.f, a2.f);
        ans.s = min(ans.s, a2.s);
    }

    return ans;
}

ii queryHoriz(int p, int i, int j, int k, int l) {
    return qry(p, i, j, k, l, horiz);
}
ii queryVert(int p, int i, int j, int k, int l) {
    return qry(p, i, j, k, l, vert);
}

void upd(int p, int i, int j, int x, int y, int v, set<int> s[]) {
    if (i > y || j < x) return;
    if (x <= i && j <= y) {
        s[p].insert(v);
        return;
    }
    if (i != j) {
        upd(p << 1, i, (i+j)/2, x, y, v, s);
        upd(p*2+1, (i+j)/2+1, j, x, y, v, s);
    }
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int A, B; cin >> A >> B;
    int n; cin >> n;

    for (int i = 1; i < 4*maxn; i++) {
        vert[i].insert(0); vert[i].insert(A);
        horiz[i].insert(0); horiz[i].insert(B);
    }

    for (int i = 0; i < n; i++) {
        int x, y, d; cin >> x >> y >> d;
        ii yBound = queryHoriz(1, 1, A-1, x, y);
        ii xBound = queryVert(1, 1, B-1, y, x);
        if (d == 1) {
            long long w = xBound.s - xBound.f;
            long long a = w*(y-yBound.f), b = w*(yBound.s-y);
            cout << min(a, b) << " " << max(a, b) << "\n";
            upd(1, 1, A-1, xBound.f, xBound.s, y, horiz);
        } else {
            long long h = yBound.s - yBound.f;
            long long a = h*(x-xBound.f), b = h*(xBound.s-x);
            cout << min(a, b) << " " << max(a, b) << "\n";
            upd(1, 1, B-1, yBound.f, yBound.s, x, vert);
        }
    }

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12