oj.uz

Submission #1011135

# Submission time Handle Problem Language Result Execution time Memory
1011135 2024-06-29T21:33:50 Z Roman70 trapezoid (balkan11_trapezoid) C++17
0 / 100
 83 ms 4436 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 1 ms 508 KB Output isn't correct
5 Incorrect 2 ms 348 KB Output isn't correct
6 Incorrect 3 ms 348 KB Output isn't correct
7 Incorrect 3 ms 348 KB Output isn't correct
8 Incorrect 4 ms 604 KB Output isn't correct
9 Incorrect 9 ms 860 KB Output isn't correct
10 Incorrect 15 ms 1516 KB Output isn't correct
11 Incorrect 21 ms 1628 KB Output isn't correct
12 Incorrect 40 ms 3000 KB Output isn't correct
13 Incorrect 61 ms 2652 KB Output isn't correct
14 Incorrect 57 ms 3668 KB Output isn't correct
15 Incorrect 63 ms 4180 KB Output isn't correct
16 Incorrect 67 ms 4000 KB Output isn't correct
17 Incorrect 82 ms 4436 KB Output isn't correct
18 Incorrect 83 ms 3404 KB Output isn't correct
19 Incorrect 78 ms 3152 KB Output isn't correct
20 Incorrect 80 ms 4312 KB Output isn't correct