Submission #83748

#	Time	Username	Problem	Language	Result	Execution time	Memory
83748		popovicirobert	trapezoid (balkan11_trapezoid)	C++14	100 / 100	241 ms	36484 KiB

trapezoid

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MOD = 30013;
const int MAXN = (int) 1e5;

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

struct Data {
    int a, b, c, d;
}arr[MAXN + 1];

int ord1[MAXN + 1], ord2[MAXN + 1];

bool cmp1(int a, int b) {
    return arr[a].b < arr[b].b;
}

bool cmp2(int a, int b) {
    return arr[a].a < arr[b].a;
}

map <int, int> mp;
int nrm[2 * MAXN + 1];

pair <int, int> aib[2 * MAXN + 1];

inline void update(int pos, int sz, pair <int, int> cur) {
    for(int i = pos; i <= sz; i += lsb(i)) {
        if(aib[i].first < cur.first) {
            aib[i] = cur;
        }
        else if(aib[i].first == cur.first) {
            aib[i].second += cur.second;
            mod(aib[i].second);
        }
    }
}

inline pair <int, int> query(int pos) {
    pair <int, int> ans = {0, 0};
    for(int i = pos; i > 0; i -= lsb(i)) {
        if(ans.first < aib[i].first) {
            ans = aib[i];
        }
        else if(ans.first == aib[i].first) {
            ans.second += aib[i].second;
            mod(ans.second);
        }
    }
    return ans;
}

pair <int, int> dp[MAXN + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin >> n;
    int sz = 0;
    for(i = 1; i <= n; i++) {
        cin >> arr[i].a >> arr[i].b >> arr[i].c >> arr[i].d;
        ord1[i] = ord2[i] = i;
        nrm[++sz] = arr[i].c;
        nrm[++sz] = arr[i].d;
    }
    sort(nrm + 1, nrm + sz + 1);
    int cur = 0;
    for(i = 1; i <= sz; i++) {
        if(nrm[i] != nrm[i - 1]) {
            cur++;
        }
        mp[nrm[i]] = cur;
    }
    sort(ord1 + 1, ord1 + n + 1, cmp1);
    sort(ord2 + 1, ord2 + n + 1, cmp2);
    int p = 1;
    for(i = 1; i <= n; i++) {
        while(p <= n && arr[ord1[p]].b < arr[ord2[i]].a) {
            update(mp[arr[ord1[p]].d], sz, dp[ord1[p]]);
            p++;
        }
        dp[ord2[i]] = query(mp[arr[ord2[i]].c] - 1);
        if(dp[ord2[i]].first == 0) {
            dp[ord2[i]] = {1, 1};
        }
        else {
            dp[ord2[i]].first++;
        }
    }
    pair <int, int> ans = {0, 0};
    for(i = 1; i <= n; i++) {
        if(ans.first < dp[i].first) {
            ans = dp[i];
        }
        else if(ans.first == dp[i].first) {
            ans.second += dp[i].second;
            mod(ans.second);
        }
    }
    cout << ans.first << " " << ans.second;
    //cin.close();
    //cout.close();
    return 0;
}

• Subtask 1: 100 / 100