#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 = 4e5+69;
pii fen[MAXN+5];
int id[MAXN];
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
//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);
memset(id, -1, sizeof(id));
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 < (int)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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 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 |
1964 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2132 KB |
Output is correct |
| 6 |
Correct |
5 ms |
2228 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2260 KB |
Output is correct |
| 8 |
Correct |
6 ms |
2388 KB |
Output is correct |
| 9 |
Correct |
14 ms |
2852 KB |
Output is correct |
| 10 |
Correct |
26 ms |
3584 KB |
Output is correct |
| 11 |
Correct |
26 ms |
4424 KB |
Output is correct |
| 12 |
Correct |
67 ms |
6548 KB |
Output is correct |
| 13 |
Correct |
71 ms |
8096 KB |
Output is correct |
| 14 |
Correct |
103 ms |
9296 KB |
Output is correct |
| 15 |
Correct |
89 ms |
8612 KB |
Output is correct |
| 16 |
Correct |
99 ms |
9660 KB |
Output is correct |
| 17 |
Correct |
106 ms |
10720 KB |
Output is correct |
| 18 |
Correct |
97 ms |
8964 KB |
Output is correct |
| 19 |
Correct |
112 ms |
10416 KB |
Output is correct |
| 20 |
Correct |
113 ms |
11200 KB |
Output is correct |
