제출 #1011135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1011135		Roman70	사다리꼴 (balkan11_trapezoid)	C++17	0 / 100	83 ms	4436 KiB

trapezoid

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Trapezoid {
    int a, b, c, d;
};

bool compare(const Trapezoid& t1, const Trapezoid& t2) {
    return t1.c < t2.c;
}

const int MAX_N = 100000;
const int MOD = 30013;

int tree[4 * MAX_N];
int lazy[4 * MAX_N];

void update(int node, int start, int end, int l, int r, int val) {
    if (lazy[node] != 0) {
        tree[node] += lazy[node];
        if (start != end) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }

    if (start > r || end < l) return;

    if (start >= l && end <= r) {
        tree[node] += val;
        if (start != end) {
            lazy[2 * node] += val;
            lazy[2 * node + 1] += val;
        }
        return;
    }

    int mid = (start + end) / 2;
    update(2 * node, start, mid, l, r, val);
    update(2 * node + 1, mid + 1, end, l, r, val);

    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

int query(int node, int start, int end, int l, int r) {
    if (lazy[node] != 0) {
        tree[node] += lazy[node];
        if (start != end) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }

    if (start > r || end < l) return -1;

    if (start >= l && end <= r) return tree[node];

    int mid = (start + end) / 2;
    int left = query(2 * node, start, mid, l, r);
    int right = query(2 * node + 1, mid + 1, end, l, r);

    return max(left, right);
}

int main() {
    int N;
    cin >> N;

    vector<Trapezoid> trapezoids(N);
    for (int i = 0; i < N; i++) {
        cin >> trapezoids[i].a >> trapezoids[i].b >> trapezoids[i].c >> trapezoids[i].d;
    }

    sort(trapezoids.begin(), trapezoids.end(), compare);

    int max_cardinality = 0;
    int max_count = 1;

    for (int i = 0; i < N; i++) {
        int curr_cardinality = query(1, 0, N - 1, 0, trapezoids[i].a - 1) + 1;
        update(1, 0, N - 1, trapezoids[i].a, trapezoids[i].b, 1);

        if (curr_cardinality > max_cardinality) {
            max_cardinality = curr_cardinality;
            max_count = 1;
        } else if (curr_cardinality == max_cardinality) {
            max_count = (max_count + 1) % MOD;
        }
    }

    cout << max_cardinality << " " << max_count << endl;

    return 0;
}

• Subtask 1: 0 / 100