#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int MX = 400042;
const int MOD = 30013;
int n;
pair<int, ll> bit[MX];
struct Trap {
int topL;
int topR;
int botL;
int botR;
bool operator<(const Trap& other) const {
return topL < other.topL;
}
} ls[100042];
int trapId[MX];
pair<int, ll> toSet[MX];
void add(int idx, pair<int, ll> val) {
for (++idx; idx < MX; idx += (idx & -idx)) {
if (bit[idx].fi == val.fi)
bit[idx].se = (bit[idx].se + val.se) % MOD;
else if (bit[idx].fi < val.fi)
bit[idx].se = val.se % MOD;
bit[idx].fi = max(bit[idx].fi, val.fi);
}
}
pair<int, ll> query(int idx) {
pair<int, int> ans {-1, 0};
for (++idx; idx > 0; idx -= (idx & -idx)) {
if (bit[idx].fi == ans.fi)
ans.se = (ans.se + bit[idx].se) % MOD;
else if (bit[idx].fi > ans.fi)
ans.se = bit[idx].se;
ans.fi = max(ans.fi, bit[idx].fi);
}
return ans;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
memset(trapId, -1, sizeof(trapId));
vector<int> coords {};
for (int i = 0; i < n; i++) {
cin >> ls[i].topL >> ls[i].topR >> ls[i].botL >> ls[i].botR;
coords.push_back(ls[i].topL);
coords.push_back(ls[i].topR);
coords.push_back(ls[i].botL);
coords.push_back(ls[i].botR);
}
ls[n] = {0, 0, 0, 0};
ls[n + 1] = {(int)1e9 + 1, (int)1e9 + 1, (int)1e9 + 1, (int)1e9 + 1};
coords.push_back(0);
coords.push_back(1e9 + 1);
sort(coords.begin(), coords.end());
coords.resize(unique(coords.begin(), coords.end()) - coords.begin());
for (int i = 0; i <= n + 1; i++) {
ls[i].topL = lower_bound(coords.begin(), coords.end(), ls[i].topL) - coords.begin();
ls[i].topR = lower_bound(coords.begin(), coords.end(), ls[i].topR) - coords.begin();
ls[i].botL = lower_bound(coords.begin(), coords.end(), ls[i].botL) - coords.begin();
ls[i].botR = lower_bound(coords.begin(), coords.end(), ls[i].botR) - coords.begin();
trapId[ls[i].topL] = i;
trapId[ls[i].topR] = i;
}
add(0, {1, 1});
for (int i = 1; i < (int)coords.size(); i++) {
if (trapId[i] != -1) {
int id = trapId[i];
auto cur = ls[id];
if (i == cur.topL) {
auto dpVal = query(cur.botL);
dpVal.first++;
toSet[cur.topR] = dpVal;
}
if (i == cur.topR) {
add(cur.botR, toSet[cur.topR]);
}
}
}
auto bst = query(MX - 2);
cout << bst.fi - 2 << ' ' << (bst.se % MOD) << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2004 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2004 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2260 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2480 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2388 KB |
Output is correct |
| 8 |
Correct |
6 ms |
2676 KB |
Output is correct |
| 9 |
Correct |
11 ms |
3416 KB |
Output is correct |
| 10 |
Correct |
20 ms |
4428 KB |
Output is correct |
| 11 |
Correct |
32 ms |
5940 KB |
Output is correct |
| 12 |
Correct |
54 ms |
9812 KB |
Output is correct |
| 13 |
Correct |
68 ms |
11340 KB |
Output is correct |
| 14 |
Correct |
80 ms |
13508 KB |
Output is correct |
| 15 |
Correct |
87 ms |
13012 KB |
Output is correct |
| 16 |
Correct |
100 ms |
14304 KB |
Output is correct |
| 17 |
Correct |
100 ms |
16356 KB |
Output is correct |
| 18 |
Correct |
89 ms |
12640 KB |
Output is correct |
| 19 |
Correct |
102 ms |
14656 KB |
Output is correct |
| 20 |
Correct |
136 ms |
17088 KB |
Output is correct |
