Submission #222969

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
222969	2020-04-14T12:32:59 Z	dolphingarlic	trapezoid (balkan11_trapezoid)	C++14	100 / 100	154 ms	10104 KB

trapezoid

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

const int MOD = 30013;

struct Trapezoid {
    int x1, x2, y1, y2;
} traps[100001];

int n, top[200001], bottom[200001];

int g_len[200001], g_num[200001];
int l_len[200001], l_num[200001];
pair<int, int> events[200001];

void update(int pos, int len, int num) {
    for (; pos < 2 * n; pos += (pos & (-pos))) {
        if (g_len[pos] == len) {
            g_num[pos] = (g_num[pos] + num) % MOD;
        } else if (g_len[pos] < len) {
            g_len[pos] = len;
            g_num[pos] = num;
        }
    }
}

pair<int, int> query(int pos) {
    pair<int, int> ans;
    for (; pos; pos -= (pos & (-pos))) {
        if (g_len[pos] == ans.first)
            ans.second = (ans.second + g_num[pos]) % MOD;
        else if (g_len[pos] > ans.first)
            ans = {g_len[pos], g_num[pos]};
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    FOR(i, 1, n + 1) {
        cin >> traps[i].x1 >> traps[i].x2 >> traps[i].y1 >> traps[i].y2;
        top[2 * i - 1] = traps[i].x1, top[2 * i] = traps[i].x2;
        bottom[2 * i - 1] = traps[i].y1, bottom[2 * i] = traps[i].y2;
    }
    sort(top + 1, top + 2 * n + 1);
    sort(bottom + 1, bottom + 2 * n + 1);
    FOR(i, 1, n + 1) {
        traps[i].x1 = lower_bound(top + 1, top + 2 * n + 1, traps[i].x1) - top;
        traps[i].x2 = lower_bound(top + 1, top + 2 * n + 1, traps[i].x2) - top;
        traps[i].y1 = lower_bound(bottom + 1, bottom + 2 * n + 1, traps[i].y1) - bottom;
        traps[i].y2 = lower_bound(bottom + 1, bottom + 2 * n + 1, traps[i].y2) - bottom;
    }

    FOR(i, 1, n + 1) {
        events[2 * i - 1] = {traps[i].x1, i};
        events[2 * i] = {traps[i].x2, -i};
    }
    sort(events + 1, events + 2 * n + 1);

    int b_len = 0, b_num = 0;
    FOR(i, 1, 2 * n + 1) {
        if (events[i].second > 0) {
            pair<int, int> lis = query(traps[events[i].second].y1);
            if (!lis.first) lis.second = 1;
            lis.first++;
            l_len[events[i].second] = lis.first;
            l_num[events[i].second] = lis.second;
            if (lis.first > b_len) {
                b_len = lis.first;
                b_num = 0;
            }
            if (lis.first == b_len) b_num = (b_num + lis.second) % MOD;
        } else update(traps[-events[i].second].y2, l_len[-events[i].second], l_num[-events[i].second]);
    }

    cout << b_len << ' ' << b_num;
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	6 ms	512 KB	Output is correct
5	Correct	7 ms	512 KB	Output is correct
6	Correct	8 ms	640 KB	Output is correct
7	Correct	9 ms	768 KB	Output is correct
8	Correct	11 ms	896 KB	Output is correct
9	Correct	17 ms	1280 KB	Output is correct
10	Correct	31 ms	2296 KB	Output is correct
11	Correct	39 ms	2808 KB	Output is correct
12	Correct	73 ms	5112 KB	Output is correct
13	Correct	92 ms	6196 KB	Output is correct
14	Correct	109 ms	7416 KB	Output is correct
15	Correct	115 ms	7672 KB	Output is correct
16	Correct	126 ms	8160 KB	Output is correct
17	Correct	130 ms	8696 KB	Output is correct
18	Correct	134 ms	9204 KB	Output is correct
19	Correct	133 ms	9592 KB	Output is correct
20	Correct	154 ms	10104 KB	Output is correct