#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];
vector<int> id(MAXN,-1);
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:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for (int i = 1; i < coords.size();++i) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1492 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1660 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1756 KB |
Output is correct |
| 9 |
Correct |
10 ms |
2404 KB |
Output is correct |
| 10 |
Correct |
19 ms |
3416 KB |
Output is correct |
| 11 |
Correct |
26 ms |
4420 KB |
Output is correct |
| 12 |
Correct |
57 ms |
7200 KB |
Output is correct |
| 13 |
Runtime error |
59 ms |
9872 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
58 ms |
11152 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
85 ms |
11828 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
72 ms |
12480 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
76 ms |
13120 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
86 ms |
13728 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
85 ms |
14360 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
77 ms |
14972 KB |
Execution killed with signal 11 |
