Submission #39770

#	Time	Username	Problem	Language	Result	Execution time	Memory
39770		krauch	trapezoid (balkan11_trapezoid)	C++14	100 / 100	262 ms	40332 KiB

trapezoid

#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 / 100