제출 #1335511

#제출 시각아이디문제언어결과실행 시간메모리
1335511rwang사다리꼴 (balkan11_trapezoid)C++20
76 / 100
83 ms6332 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5, MOD = 30013;

struct Segment {
    int val, cnt;
} segtree[4 * N];

const Segment DEFAULT = {0, 1};

Segment merge(const Segment& a, const Segment& b) {
    if (a.val > b.val) {
        return a;
    }
    if (b.val > a.val) {
        return b;
    }
    return {a.val, (a.cnt + b.cnt) % MOD};
}

void update(int i, int l, int r, int x, Segment v) {
    if (l == r) {
        segtree[i] = v;
        return;
    }
    int m = (l + r) / 2;
    if (x <= m) {
        update(2 * i, l, m, x, v);
    } else {
        update(2 * i + 1, m + 1, r, x, v);
    }
    segtree[i] = merge(segtree[2 * i], segtree[2 * i + 1]);
}

Segment query(int i, int l, int r, int x, int y) {
    if (x > y) {
        return DEFAULT;
    }
    if (l == x && r == y) {
        return segtree[i];
    }
    int m = (l + r) / 2;
    return merge(
        query(2 * i, l, m, x, min(m, y)),
        query(2 * i + 1, m + 1, r, max(m + 1, x), y)
    );
}

struct Event {
    int x, y, i;
    bool operator<(const Event& t) const {
        return x < t.x;
    }
};

vector<int> indices;

int idx(int i) {
    return upper_bound(indices.begin(), indices.end(), i) - indices.begin() - 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    Segment val[N]{};
    vector<Event> events;
    for (int i = 0; i < n; i++) {
        int x1, x2, y1, y2;
        cin >> x1 >> x2 >> y1 >> y2;
        events.push_back({x1, y1, i});
        events.push_back({x2, y2, i});
        indices.push_back(y2);
    }
    sort(events.begin(), events.end());
    sort(indices.begin(), indices.end());
    indices.erase(unique(indices.begin(), indices.end()), indices.end());
    int m = (int) indices.size();
    for (Event e : events) {
        if (val[e.i].cnt == 0) {
            val[e.i] = query(1, 0, m - 1, 0, idx(e.y));
            val[e.i].val++;
        } else {
            update(1, 0, m - 1, idx(e.y), val[e.i]);
        }
    }
    Segment ans = query(1, 0, m - 1, 0, m - 1);
    cout << ans.val << " " << ans.cnt;
}
#Verdict Execution timeMemoryGrader output
Fetching results...