Submission #83748

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
83748	2018-11-10T10:39:29 Z	popovicirobert	trapezoid (balkan11_trapezoid)	C++14	100 / 100	241 ms	36484 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	352 KB	Output is correct
2	Correct	2 ms	528 KB	Output is correct
3	Correct	3 ms	640 KB	Output is correct
4	Correct	3 ms	796 KB	Output is correct
5	Correct	5 ms	1180 KB	Output is correct
6	Correct	6 ms	1376 KB	Output is correct
7	Correct	10 ms	1540 KB	Output is correct
8	Correct	13 ms	1716 KB	Output is correct
9	Correct	18 ms	2844 KB	Output is correct
10	Correct	34 ms	4804 KB	Output is correct
11	Correct	57 ms	6176 KB	Output is correct
12	Correct	110 ms	11248 KB	Output is correct
13	Correct	133 ms	14396 KB	Output is correct
14	Correct	171 ms	18024 KB	Output is correct
15	Correct	178 ms	20648 KB	Output is correct
16	Correct	201 ms	23432 KB	Output is correct
17	Correct	209 ms	26540 KB	Output is correct
18	Correct	173 ms	29696 KB	Output is correct
19	Correct	208 ms	33004 KB	Output is correct
20	Correct	241 ms	36484 KB	Output is correct