oj.uz

답안 #222969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
222969 2020-04-14T12:32:59 Z dolphingarlic 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 154 ms 10104 KB 
#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

# 결과 실행 시간 메모리 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