oj.uz

Submission #254464

# Submission time Handle Problem Language Result Execution time Memory
254464 2020-07-30T04:31:50 Z thecodingwizard Krave (COI14_krave) C++11
100 / 100
 1139 ms 155384 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 113144 KB Output is correct
2 Correct 161 ms 113108 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 113436 KB Output is correct
2 Correct 164 ms 114040 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 118612 KB Output is correct
2 Correct 290 ms 118520 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 118608 KB Output is correct
2 Correct 315 ms 119272 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 118648 KB Output is correct
2 Correct 325 ms 120056 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 127352 KB Output is correct
2 Correct 521 ms 142072 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1094 ms 142328 KB Output is correct
2 Correct 586 ms 146796 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1018 ms 141560 KB Output is correct
2 Correct 543 ms 151672 KB Output is correct
3 Correct 314 ms 120568 KB Output is correct
4 Correct 650 ms 149000 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1139 ms 142584 KB Output is correct
2 Correct 593 ms 155384 KB Output is correct
3 Correct 307 ms 120908 KB Output is correct
4 Correct 617 ms 151416 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1038 ms 142840 KB Output is correct
2 Correct 476 ms 145912 KB Output is correct
3 Correct 297 ms 120952 KB Output is correct
4 Correct 646 ms 153592 KB Output is correct