oj.uz

Submission #553928

# Submission time Handle Problem Language Result Execution time Memory
553928 2022-04-27T11:21:54 Z zxcvbnm Krave (COI14_krave) C++14
100 / 100
 961 ms 121044 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Rect {
    int x1, y1, x2, y2;

    Rect() {};
    Rect(int X1, int Y1, int X2, int Y2) : x1(X1), y1(Y1), x2(X2), y2(Y2) {};
    bool operator<(const Rect& other) const {
        return vector<int>{x1, y1, x2, y2} < vector<int>{other.x1, other.y1, other.x2, other.y2};
    }

    void print() const {
        cout << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
    }

    ll area() const {
        return (ll) (x2 - x1) * (ll) (y2 - y1);
    }
};

struct St {
    int n;
    vector<set<int, greater<int>>> tree;

    St(int sz) {
        n = 1;
        while(n < sz) {
            n *= 2;
        }

        tree.assign(2*n, {0});
    }

    void add(int L, int R, int val) {
        add_r(0, n, 0, L, R, val);
    }

    void add_r(int l, int r, int idx, int L, int R, int val) {
        if (l >= R || L >= r) return;
        if (l >= L && R >= r) {
//            cout << "add: " << l << " " << r << " " << val << "\n";
            tree[idx].insert(val);
            return;
        }

        int mid = (l + r) / 2;
        add_r(l, mid, 2*idx+1, L, R, val);
        add_r(mid, r, 2*idx+2, L, R, val);
    }

    int get(int id, int val) {
        return get_r(0, n, 0, id, val);
    }

    int get_r(int l, int r, int idx, int id, int val) {
        int curr = 0;
        if (id >= l && r >= id) {
            curr = *tree[idx].lower_bound(val);
        }

        if (r - l == 1) return curr;

        int mid = (l + r) / 2;
        if (id < mid) {
            return max(curr, get_r(l, mid, 2*idx+1, id, val));
        }
        else {
            return max(curr, get_r(mid, r, 2*idx+2, id, val));
        }
    }

};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;

    set<Rect> s;
    s.insert(Rect(0, 0, n, m));

    St down(n);
    St left(m);

    int q;
    cin >> q;
    while(q--) {
        int x, y, d;
        cin >> x >> y >> d;

        int X = left.get(y, x);
        int Y = down.get(x, y);
        auto it = s.lower_bound({X, Y, 0, 0});
        s.erase(it);

//        cout << X << " " << Y << " " << x << " " << y << "\n";
//        cout << "rect: ";
//        it->print();

        if (d == 1) {
            Rect a(it->x1, it->y1, it->x2, y);
            Rect b(it->x1, y, it->x2, it->y2);

//            cout << "a: ";
//            a.print();
//            cout << "b: ";
//            b.print();

            down.add(it->x1, it->x2, y);
            s.insert(a);
            s.insert(b);

            ll aa = a.area(), bb = b.area();
            if (aa > bb) {
                swap(aa, bb);
            }

            cout << aa << " " << bb << "\n";
        }
        else {
            Rect a(it->x1, it->y1, x, it->y2);
            Rect b(x, it->y1, it->x2, it->y2);

            left.add(it->y1, it->y2, x);
            s.insert(a);
            s.insert(b);

//            cout << "a: ";
//            a.print();
//            cout << "b: ";
//            b.print();

            ll aa = a.area(), bb = b.area();
            if (aa > bb) {
                swap(aa, bb);
            }

            cout << aa << " " << bb << "\n";
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 1 ms 448 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 50116 KB Output is correct
2 Correct 47 ms 50460 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 64984 KB Output is correct
2 Correct 439 ms 79132 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 64932 KB Output is correct
2 Correct 473 ms 79512 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 64932 KB Output is correct
2 Correct 628 ms 100248 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 66564 KB Output is correct
2 Correct 607 ms 98604 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 961 ms 84384 KB Output is correct
2 Correct 667 ms 101848 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 891 ms 83408 KB Output is correct
2 Correct 462 ms 89676 KB Output is correct
3 Correct 499 ms 60552 KB Output is correct
4 Correct 711 ms 105260 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 916 ms 84464 KB Output is correct
2 Correct 516 ms 94056 KB Output is correct
3 Correct 561 ms 74768 KB Output is correct
4 Correct 836 ms 120696 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 941 ms 84688 KB Output is correct
2 Correct 412 ms 84064 KB Output is correct
3 Correct 593 ms 87156 KB Output is correct
4 Correct 864 ms 121044 KB Output is correct