oj.uz

Submission #249733

# Submission time Handle Problem Language Result Execution time Memory
249733 2020-07-15T16:16:17 Z apostoldaniel854 trapezoid (balkan11_trapezoid) C++14
100 / 100
 321 ms 27256 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int N = 1e5;
const int START = 0, FINISH = 1;
const int MOD = 30013;

struct Node {
    int best;
    int cnt;
};
Node join (Node a, Node b) {
    Node c = a;
    if (c.best < b.best)
        c.best = b.best, c.cnt = 0;
    if (c.best == b.best) {
        c.cnt += b.cnt;
        if (c.cnt >= MOD)
            c.cnt -= MOD;
    }
    return c;
};
Node aib[1 + 2 * N];
int lsb (int x) {
    return x & -x;
}
int n;
void upd (int pos, Node value) {
    while (pos <= 2 * n) {
        aib[pos] = join (aib[pos], value);
        pos += lsb (pos);
    }
}
Node qry (int pos) {
    Node ans = {0, 0};
    while (pos) {
        ans = join (ans, aib[pos]);
        pos -= lsb (pos);
    }
    return ans;
}

struct Trapezoid {
    int x1;
    int y1;
    int x2;
    int y2;
};
Trapezoid trap[1 + N];
pair <int, int> event[1 + 2 * N];
Node dp[1 + N];
int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    cin >> n;
    map <int, int> mpTop, mpBottom;
    for (int i = 1; i <= n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        trap[i] = {x1, y1, x2, y2};
        mpTop[x1] = 0;
        mpTop[y1] = 0;
        mpBottom[x2] = 0;
        mpBottom[y2] = 0;
    }

    int nr = 0;
    for (auto &x : mpTop) x.second = ++nr;
    nr = 0;
    for (auto &x : mpBottom) x.second = ++nr;
    for (int i = 1; i <= n; i++) {
        trap[i].x1 = mpTop[trap[i].x1];
        trap[i].y1 = mpTop[trap[i].y1];
        trap[i].x2 = mpBottom[trap[i].x2];
        trap[i].y2 = mpBottom[trap[i].y2];
        event[trap[i].x1] = {i, START};
        event[trap[i].y1] = {i, FINISH};
    }
    for (int i = 1; i <= 2 * n; i++) {
        int index = event[i].first;
        int type = event[i].second;
        if (type == START) {
            dp[index] = qry (trap[index].x2);
            if (not dp[index].cnt)
                dp[index].cnt++;
            dp[index].best++;
        }
        if (type == FINISH)
            upd (trap[index].y2, dp[index]);
    }
    Node ans = {0, 0};
    for (int i = 1; i <= n; i++)
        ans = join (ans, dp[i]);
    cout << ans.best << " " << ans.cnt << "\n";
    return 0;
}
/**
    7
    1 3 1 9
    4 7 2 8
    11 15 4 12
    10 12 15 19
    16 23 16 22
    20 22 13 25
    30 31 30 31
**/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 4 ms 896 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 9 ms 1408 KB Output is correct
8 Correct 11 ms 1664 KB Output is correct
9 Correct 21 ms 3072 KB Output is correct
10 Correct 56 ms 5752 KB Output is correct
11 Correct 56 ms 7032 KB Output is correct
12 Correct 138 ms 13816 KB Output is correct
13 Correct 174 ms 16504 KB Output is correct
14 Correct 207 ms 19336 KB Output is correct
15 Correct 253 ms 20508 KB Output is correct
16 Correct 281 ms 21880 KB Output is correct
17 Correct 276 ms 23288 KB Output is correct
18 Correct 242 ms 24568 KB Output is correct
19 Correct 283 ms 25848 KB Output is correct
20 Correct 321 ms 27256 KB Output is correct