oj.uz

Submission #39770

# Submission time Handle Problem Language Result Execution time Memory
39770 2018-01-18T11:40:24 Z krauch trapezoid (balkan11_trapezoid) C++14
100 / 100
 262 ms 40332 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int, int > PII;

#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define F first
#define S second
#define mkp make_pair
#define eb emplace_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()

const int N = 1e6 + 6, base = 30013;

struct trap {
    int ul, ur, dl, dr;
    trap(){}
} a[N];


int n, g[N];
PII d[N], t[N];
vector < int > vec;

bool cmp(trap a, trap b) {
    return a.ul < b.ul;
}

void upd(int i, PII val) {
    for (; i <= sz(vec); i |= i + 1) {
        if (val.S < t[i].S) continue;
        if (val.S == t[i].S) t[i].F = (t[i].F + val.F) % base;
        else t[i] = val;
    }
}

PII get(int i) {
    PII res = PII(1, 0);
    for (; i >= 0; i = (i & (i + 1)) - 1) {
        if (res.S > t[i].S) continue;
        if (res.S == t[i].S) res.F = (res.F + t[i].F) % base;
        else res = t[i];
    }
    return res;
}

int main() {

    cin >> n;
    forn(i, 1, n) {
        cin >> a[i].ul >> a[i].ur >> a[i].dl >> a[i].dr;
        d[i] = PII(1, 1);
        vec.eb(a[i].ul);
        vec.eb(a[i].ur);
        vec.eb(a[i].dl);
        vec.eb(a[i].dr);
    }

    sort(all(vec));

    forn(i, 1, n) {
        a[i].ul = lower_bound(all(vec), a[i].ul) - vec.begin() + 1;
        a[i].ur = lower_bound(all(vec), a[i].ur) - vec.begin() + 1;
        a[i].dl = lower_bound(all(vec), a[i].dl) - vec.begin() + 1;
        a[i].dr = lower_bound(all(vec), a[i].dr) - vec.begin() + 1;
        g[a[i].ul] = i;
        g[a[i].ur] = i;
    }

    forn(i, 1, sz(vec)) {
        if (a[g[i]].ul == i) {
            d[g[i]] = get(a[g[i]].dl);
            d[g[i]].S++;
        }
        else {
            upd(a[g[i]].dr, d[g[i]]);
        }
    }
    int mx = 0;
    forn(i, 1, n) mx = max(mx, d[i].S);
    int ans = 0;
    forn(i, 1, n) if (d[i].S == mx) ans = (ans + d[i].F) % base;

    cout << mx << " " << ans << "\n";

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37176 KB Output is correct
2 Correct 0 ms 37176 KB Output is correct
3 Correct 1 ms 37176 KB Output is correct
4 Correct 2 ms 37176 KB Output is correct
5 Correct 4 ms 37316 KB Output is correct
6 Correct 4 ms 37316 KB Output is correct
7 Correct 6 ms 37316 KB Output is correct
8 Correct 12 ms 37448 KB Output is correct
9 Correct 20 ms 37644 KB Output is correct
10 Correct 48 ms 38028 KB Output is correct
11 Correct 65 ms 38028 KB Output is correct
12 Correct 129 ms 38796 KB Output is correct
13 Correct 156 ms 38796 KB Output is correct
14 Correct 185 ms 40332 KB Output is correct
15 Correct 207 ms 40332 KB Output is correct
16 Correct 221 ms 40332 KB Output is correct
17 Correct 262 ms 40332 KB Output is correct
18 Correct 224 ms 40332 KB Output is correct
19 Correct 239 ms 40332 KB Output is correct
20 Correct 262 ms 40332 KB Output is correct