Submission #1199017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199017		primovocatus	trapezoid (balkan11_trapezoid)	C++20	60 / 100	94 ms	12832 KiB

trapezoid

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int mod = 30013;
const int N = 1e5 + 5;

pair<int, int> a[N], b[N], t[N];
pair<int, int> dp[N];
 
int addf(int a, int b) {
    return a + b >= mod ? a + b - mod : a + b;
}

void addt(int l, int len, int cnt) {
    for ( ; l < N; l |= l + 1) {
        if (t[l].first < len) {
            t[l] = {len, cnt};
        } else if (t[l].first == len) {
            t[l].second = addf(t[l].second, cnt);
        }
    }
}

pair<int, int> get(int r) {
    int len = 0, cnt = 1;
    for ( ; r >= 0; r = (r & (r + 1)) - 1) {
        if (len < t[r].first) {
            len = t[r].first, cnt = t[r].second;
        } else if (len == t[r].first) {
            cnt = addf(cnt, t[r].second);
        }
    }
    return {len, cnt};
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    
    int n;
    cin >> n;

    vector<int> x, y;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second >> b[i].first >> b[i].second;

        x.push_back(a[i].first);
        x.push_back(a[i].second);
        y.push_back(b[i].first);
        y.push_back(b[i].second);
    }

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());

    x.erase(unique(x.begin(), x.end()), x.end());
    y.erase(unique(y.begin(), y.end()), y.end());

    for (int i = 0; i < n; ++i) {
        a[i].first = lower_bound(x.begin(), x.end(), a[i].first) - x.begin();
        a[i].second = lower_bound(x.begin(), x.end(), a[i].second) - x.begin();
        b[i].first = lower_bound(y.begin(), y.end(), b[i].first) - y.begin();
        b[i].second = lower_bound(y.begin(), y.end(), b[i].second) - y.begin();
    }

    vector<pair<int, int>> event;
    for (int i = 0; i < n; ++i) {
        event.push_back({a[i].first, -i - 1});
        event.push_back({a[i].second, i + 1});
    }

    sort(event.begin(), event.end());

    pair<int, int> ans = {0, 1};
    for (int i = 0; i < 2 * n; ++i) {
        int x = event[i].first;
        int type = event[i].second;

        if (type < 0) {
            type = -type;
            pair<int, int> g = get(b[type - 1].first);
            g.first++;

            dp[type - 1] = g;
        
            if (g.first > ans.first) {
                ans = g;
            } else if (g.first == ans.first) {
                ans.second = addf(ans.second, g.second);
            }
        } else {
            addt(b[type - 1].second, dp[type - 1].first, dp[type - 1].second);
        }
    }

    cout << ans.first << " " << ans.second << "\n";

    return 0;
}

• Subtask 1: 60 / 100