Submission #553928

#	Time	Username	Problem	Language	Result	Execution time	Memory
553928		zxcvbnm	Krave (COI14_krave)	C++14	100 / 100	961 ms	121044 KiB

krave

#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 / 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