#include <bits/stdc++.h>
using namespace std;
#define ll long long
using pii = pair<int,long long>;
const int MOD = 30013;
const int INF = 1e9+7;
const int MAXN = 2e5+69;
pii fen[MAXN+5];
void upd(int i, pii v) {
i++;
for (; i < MAXN; i += (i & -i)) {
if (fen[i].first < v.first) {
fen[i].first = v.first;
fen[i].second = v.second % MOD;
} else if (fen[i].first == v.first) {
fen[i].second += v.second;
fen[i].second %= MOD;
}
}
}
pii query(int i) {
i++;
pii ans = {-1, 0};
for (; i > 0; i -= (i & -i)) {
if (fen[i].first > ans.first) {
ans.first = fen[i].first;
ans.second = fen[i].second;
} else if (fen[i].first == ans.first) {
ans.second += fen[i].second;
ans.second %= MOD;
}
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
vector<pair<pii, pii>> v(n+2);
vector<int> a(n+2), b(n+2), c(n+2), d(n+2);
vector<int> coords;
for (int i = 0; i <n ; ++i) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
coords.push_back(a[i]);
coords.push_back(b[i]);
coords.push_back(c[i]);
coords.push_back(d[i]);
}
// to avoid using neutral element
coords.push_back(0);
coords.push_back(INF);
a[n] = b[n] = c[n] = d[n] = 0;
a[n+1] = b[n+1] = c[n+1] = d[n+1] = INF;
sort(coords.begin(), coords.end()); coords.erase(unique(coords.begin(), coords.end()));
vector<int> id(coords.size()+5,-1);
for (int i = 0; i <= n+1; ++i) {
a[i] = lower_bound(coords.begin(), coords.end(), a[i]) - coords.begin();
b[i] = lower_bound(coords.begin(), coords.end(), b[i]) - coords.begin();
c[i] = lower_bound(coords.begin(), coords.end(), c[i]) - coords.begin();
d[i] = lower_bound(coords.begin(), coords.end(), d[i]) - coords.begin();
id[a[i]] = id[b[i]] = i;
}
upd(0, {1,1}); // add trap at 0 to avoid using neutral element
vector<pii> dp(n+5);
for (int i = 1; i < coords.size();++i) {
if (id[i]==-1) continue;
int cur = id[i];
if (i == a[cur]) {
dp[cur] = query(c[cur]);
dp[cur].first++;
}
if (i == b[cur]) {
upd(d[cur], dp[cur]);
}
}
pii ans = query(MAXN-5);
cout << ans.first - 2 << " " << ans.second % MOD << "\n";
return 0;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int i = 1; i < coords.size();++i) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
2 ms |
476 KB |
Output is correct |
| 5 |
Correct |
2 ms |
596 KB |
Output is correct |
| 6 |
Correct |
3 ms |
852 KB |
Output is correct |
| 7 |
Correct |
4 ms |
988 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 9 |
Correct |
10 ms |
2008 KB |
Output is correct |
| 10 |
Correct |
19 ms |
3436 KB |
Output is correct |
| 11 |
Correct |
27 ms |
4636 KB |
Output is correct |
| 12 |
Correct |
54 ms |
8660 KB |
Output is correct |
| 13 |
Runtime error |
71 ms |
19972 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
80 ms |
21256 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
96 ms |
23368 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
97 ms |
24244 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
100 ms |
25148 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
100 ms |
25928 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
100 ms |
23844 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
119 ms |
27728 KB |
Execution killed with signal 11 |
