#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int N = 1e5, modulo = 30013;
int n, a[N + 5], b[N + 5], c[N + 5], d[N + 5];
pair<int, int> indx[2*N + 5], tree[2*N + 5], dp[N + 5];
vector<int> mp;
pair<int, int> combine(pair<int, int>&f, pair<int, int>&se) {
if (f.first == se.first) return {f.first, (f.second + se.second) % modulo};
else return f > se ? f : se;
}
void update(int k, pair<int, int> x) {
for (; k <= 2*n; k += k&-k) tree[k] = combine(tree[k], x);
}
pair<int, int> query(int k) {
pair<int, int> ans = {0, 0};
for (; k; k -= k&-k) ans = combine(ans, tree[k]);
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];
for (int i = 1; i <= 2*n; i += 2) indx[i] = {(i + 1)/2, 0}, indx[i + 1] = {(i + 1)/2, 1};
sort(indx + 1, indx + 2*n + 1, [&](pair<int, int>&x, pair<int, int>&y) {
int f = x.second == 0 ? a[x.first] : b[x.first];
int se = y.second == 0 ? a[y.first] : b[y.first];
return f < se;
});
for (int i = 1; i <= n; i++) mp.push_back(c[i]), mp.push_back(d[i]);
sort(mp.begin(), mp.end());
mp.erase(unique(mp.begin(), mp.end()), mp.end());
auto getIndex = [&](int p) { return lower_bound(mp.begin(), mp.end(), p) - mp.begin() + 1; };
for (int i = 1; i <= 2*n; i++) {
int index = indx[i].first, type = indx[i].second;
if (!type) {
int Y = getIndex(c[index]);
pair<int, int> res = query(Y);
if (!res.first) dp[index] = {1, 1};
else dp[index] = {res.first + 1, res.second};
} else {
int Y = getIndex(d[index]);
update(Y, dp[index]);
}
}
int mx = 0, total = 0;
for (int i = 1; i <= n; i++) {
if (mx < dp[i].first) mx = dp[i].first, total = dp[i].second;
else if (mx == dp[i].first) total += dp[i].second, total %= modulo;
}
cout << mx << " "<< total << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
2 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
596 KB |
Output is correct |
| 7 |
Correct |
3 ms |
724 KB |
Output is correct |
| 8 |
Correct |
4 ms |
724 KB |
Output is correct |
| 9 |
Correct |
9 ms |
1204 KB |
Output is correct |
| 10 |
Correct |
15 ms |
1880 KB |
Output is correct |
| 11 |
Correct |
19 ms |
2164 KB |
Output is correct |
| 12 |
Correct |
41 ms |
3716 KB |
Output is correct |
| 13 |
Correct |
50 ms |
4364 KB |
Output is correct |
| 14 |
Correct |
61 ms |
4896 KB |
Output is correct |
| 15 |
Correct |
67 ms |
5260 KB |
Output is correct |
| 16 |
Correct |
71 ms |
5576 KB |
Output is correct |
| 17 |
Correct |
74 ms |
5800 KB |
Output is correct |
| 18 |
Correct |
67 ms |
6168 KB |
Output is correct |
| 19 |
Correct |
73 ms |
6340 KB |
Output is correct |
| 20 |
Correct |
84 ms |
6760 KB |
Output is correct |
