Submission #376350

#	Time	Username	Problem	Language	Result	Execution time	Memory
376350		ja_kingy	trapezoid (balkan11_trapezoid)	C++14	100 / 100	129 ms	10852 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

const int mxN = 1e5, MOD = 30013;
int n, x[mxN][4], pts[mxN*2];
pii st[4*mxN], dp[mxN];

pii comb(pii a, pii b) {
    if (a.first != b.first) return max(a,b);
    return {a.first, (a.second + b.second) % MOD};
}

void upd(int x, pii v) {
    for (x += 2*n; x; x /= 2) st[x] = comb(st[x], v);
}

pii qry(int l, int r) {
    pii res = {0,1};
    for (l += 2*n, r += 2*n; l < r; l /= 2, r /= 2) {
        if (l&1) res = comb(res, st[l++]);
        if (r&1) res = comb(res, st[--r]);
    }
    return res;
}

int compress(int x) {
    return lower_bound(pts, pts+2*n, x) - pts;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    vector<pii> tops;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 4; ++j) {
            cin >> x[i][j];
        }
        pts[2*i] = x[i][2];
        pts[2*i+1] = x[i][3];
        tops.push_back({i,0});
        tops.push_back({i,1});
    }
    sort(pts, pts+2*n);
    sort(tops.begin(), tops.end(), [&](pii a, pii b){ return x[a.first][a.second] < x[b.first][b.second];});
    for (pii t: tops) {
        if (t.second == 0) {
            dp[t.first] = qry(0, compress(x[t.first][2]));
            dp[t.first].first = (dp[t.first].first + 1) % MOD;
        } else {
            upd(compress(x[t.first][3]), dp[t.first]);
        }
    }
    cout << st[1].first << ' ' << st[1].second << '\n';
}

• Subtask 1: 100 / 100