Submission #238789

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
238789	2020-06-12T22:03:59 Z	thecodingwizard	trapezoid (balkan11_trapezoid)	C++11	100 / 100	301 ms	19456 KB

trapezoid

#include <bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define ii pair<int, int>
#define f first
#define s second
 
const int mod = 30013;

struct BIToff {
    bool mode = 0; vector<int> v; vector<int> ft;
    int idx(int x) { return upper_bound(v.begin(), v.end(), x) - v.begin(); }
    void init() {
        mode = 1;
        sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
        ft.resize((int)v.size()+1);
    }
    void upd(int x, int y) {
        if (!mode) { v.pb(x); return; }
        int k = idx(x);
        for (; k <= (int) v.size(); k += k&-k) ft[k] = (ft[k] + y) % mod;
    }
    int sum(int x) {
        int ans = 0; for (int p = idx(x); p; p -= p&-p) ans += ft[p];
        return ans;
    }
} bits[100001];
 
int main() {
    int n; cin >> n;
    vector<ii> topLeft;
    vector<pair<ii, ii>> A;
    for (int i = 0; i < n; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        A.pb({{a,b},{c,d}});
        topLeft.pb({a,i});
    }
    sort(topLeft.begin(), topLeft.end());
 
    int tlIdx = 0;
    set<ii> q;
    map<int, int> traps;
    int dp[n];

    // 1 = add, 2 = calculate
    vector<pair<int, ii>> events;
    while (tlIdx != n) {
        while (!q.empty() && q.begin()->f < topLeft[tlIdx].f) {
            int x = q.begin()->s;
            q.erase(q.begin());
            auto it = traps.lower_bound(A[x].s.s);
            while (it != traps.end() && it->s < dp[x]) {
                it = traps.erase(it);
            }
            it = traps.lower_bound(A[x].s.s);
            if (!traps.empty()) {
                if (it != traps.begin()) {
                    it--;
                    if (it->s > dp[x]) continue;
                }
            }
            events.push_back({1, {A[x].s.s, x}});
            traps[A[x].s.s] = dp[x];
        }
 
        int u = topLeft[tlIdx].s;
        int best = 1;
        if (!traps.empty()) {
            auto it = traps.lower_bound(A[u].s.f);
            if (it != traps.begin()) {
                it--;
                best = 1 + it->s;
            }
        }
        events.push_back({2, {u,-1}});
        dp[u] = best;
        q.insert({A[u].f.s, u});
 
        tlIdx++;
    }

    ii dp2[n];
    for (auto e : events) {
        if (e.f == 1) {
            bits[dp[e.s.s]].upd(e.s.f, dp2[e.s.s].s);
        }
    }
    bits[0].upd(1,1);
    for (int i = 0; i <= n; i++) bits[i].init();
    bits[0].upd(1,1);
    for (auto e : events) {
        if (e.f == 1) {
            bits[dp[e.s.s]].upd(e.s.f, dp2[e.s.s].s);
        } else {
            dp2[e.s.f] = make_pair(dp[e.s.f], bits[dp[e.s.f]-1].sum(A[e.s.f].s.f));
        }
    }

    int ans = 0;
    int ans2 = 0;
    for (int i = 0; i < n; i++) {
        if (dp2[i].f > ans) {
            ans = dp2[i].f; ans2 = dp2[i].s;
        } else if (dp2[i].f == ans) {
            ans2 = (ans2 + dp2[i].s) % mod;
        }
    }
 
    cout << ans << " " << ans2 << endl;
 
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	5760 KB	Output is correct
2	Correct	8 ms	5888 KB	Output is correct
3	Correct	9 ms	5888 KB	Output is correct
4	Correct	10 ms	6016 KB	Output is correct
5	Correct	12 ms	6016 KB	Output is correct
6	Correct	15 ms	6272 KB	Output is correct
7	Correct	16 ms	6272 KB	Output is correct
8	Correct	18 ms	6400 KB	Output is correct
9	Correct	32 ms	7028 KB	Output is correct
10	Correct	53 ms	8172 KB	Output is correct
11	Correct	75 ms	9196 KB	Output is correct
12	Correct	132 ms	11496 KB	Output is correct
13	Correct	166 ms	13028 KB	Output is correct
14	Correct	205 ms	14820 KB	Output is correct
15	Correct	205 ms	14308 KB	Output is correct
16	Correct	215 ms	14820 KB	Output is correct
17	Correct	239 ms	15776 KB	Output is correct
18	Correct	227 ms	17324 KB	Output is correct
19	Correct	282 ms	19424 KB	Output is correct
20	Correct	301 ms	19456 KB	Output is correct