Submission #97760

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
97760	2019-02-18T10:25:14 Z	Anai	trapezoid (balkan11_trapezoid)	C++14	100 / 100	225 ms	15224 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() {
    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 << '\n';
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	512 KB	Output is correct
4	Correct	4 ms	512 KB	Output is correct
5	Correct	4 ms	640 KB	Output is correct
6	Correct	6 ms	768 KB	Output is correct
7	Correct	9 ms	896 KB	Output is correct
8	Correct	11 ms	1152 KB	Output is correct
9	Correct	18 ms	1920 KB	Output is correct
10	Correct	29 ms	3320 KB	Output is correct
11	Correct	47 ms	4088 KB	Output is correct
12	Correct	100 ms	7780 KB	Output is correct
13	Correct	127 ms	9336 KB	Output is correct
14	Correct	165 ms	10704 KB	Output is correct
15	Correct	199 ms	11548 KB	Output is correct
16	Correct	209 ms	12216 KB	Output is correct
17	Correct	204 ms	13000 KB	Output is correct
18	Correct	152 ms	13688 KB	Output is correct
19	Correct	199 ms	14352 KB	Output is correct
20	Correct	225 ms	15224 KB	Output is correct