/* In the name of Allah */
// Welcome to the Soldier Side!
// Where there's no one here, but me...
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, P = 30013;
vector<int> L[2 * N], R[2 * N], vec[N];
int n, a[N], b[N], c[N], d[N], dp[N], cnt[N];
struct MaxFenwickTree {
int fen[2 * N];
void add(int p, int k) {
for (; p < 2 * N; p += p & -p)
fen[p] = max(fen[p], k);
}
int get(int p) {
int res = 0;
for (; p; p -= p & -p)
res = max(res, fen[p]);
return res;
}
} T1;
struct SumFenwickTree {
int fen[2 * N];
vector<int> history;
void add(int p, int k) {
history.push_back(p);
for (p++; p < 2 * N; p += p & -p)
(fen[p] += k) %= P;
}
int get(int p) {
int res = 0;
for (p++; p; p -= p & -p)
(res += fen[p]) %= P;
return res;
}
void rollback() {
for (int p: history)
for (p++; p < 2 * N; p += p & -p)
fen[p] = 0;
history.clear();
}
} T2;
void compress(int x[], int y[]) {
vector<int> help;
for (int i = 0; i < n; i++) {
help.push_back(x[i]);
help.push_back(y[i]);
}
sort(help.begin(), help.end());
help.resize(unique(help.begin(), help.end()) - help.begin());
for (int i = 0; i < n; i++) {
x[i] = lower_bound(help.begin(), help.end(), x[i]) - help.begin();
y[i] = lower_bound(help.begin(), help.end(), y[i]) - help.begin();
}
}
void read_input() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i] >> b[i] >> c[i] >> d[i];
}
void solve() {
compress(a, b), compress(c, d);
for (int i = 0; i < n; i++) {
L[a[i]].push_back(i);
R[b[i]].push_back(i);
}
for (int i = 0; i < 2 * n; i++) {
for (int p: R[i])
T1.add(d[p], dp[p]);
for (int p: L[i])
dp[p] = T1.get(c[p]) + 1;
}
fill(cnt, cnt + n, 1);
for (int i = 0; i < n; i++)
vec[dp[i]].push_back(i);
for (int i = 2; i <= n; i++) {
vector<pair<int, int>> help;
for (int p: vec[i - 1])
help.push_back({b[p], p});
for (int p: vec[i])
help.push_back({a[p], p});
T2.rollback();
sort(help.begin(), help.end());
for (auto [_, p]: help)
if (dp[p] < i)
T2.add(d[p], cnt[p]);
else
cnt[p] = T2.get(c[p]);
}
}
void write_output() {
int ted = 0;
int k = *max_element(dp, dp + n);
for (int p: vec[k])
(ted += cnt[p]) %= P;
cout << k << " " << ted << endl;
}
int main() {
ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
read_input(), solve(), write_output();
return 0;
}
Compilation message
trapezoid.cpp: In function 'void solve()':
trapezoid.cpp:94:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
94 | for (auto [_, p]: help)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
23900 KB |
Output is correct |
| 2 |
Correct |
10 ms |
24068 KB |
Output is correct |
| 3 |
Correct |
12 ms |
23896 KB |
Output is correct |
| 4 |
Correct |
11 ms |
24012 KB |
Output is correct |
| 5 |
Correct |
11 ms |
24156 KB |
Output is correct |
| 6 |
Correct |
11 ms |
24156 KB |
Output is correct |
| 7 |
Correct |
13 ms |
24412 KB |
Output is correct |
| 8 |
Correct |
15 ms |
24572 KB |
Output is correct |
| 9 |
Correct |
21 ms |
25156 KB |
Output is correct |
| 10 |
Correct |
29 ms |
26660 KB |
Output is correct |
| 11 |
Correct |
34 ms |
27256 KB |
Output is correct |
| 12 |
Correct |
62 ms |
30276 KB |
Output is correct |
| 13 |
Correct |
70 ms |
30900 KB |
Output is correct |
| 14 |
Correct |
91 ms |
32944 KB |
Output is correct |
| 15 |
Correct |
91 ms |
32816 KB |
Output is correct |
| 16 |
Correct |
92 ms |
32864 KB |
Output is correct |
| 17 |
Correct |
100 ms |
33876 KB |
Output is correct |
| 18 |
Correct |
103 ms |
33644 KB |
Output is correct |
| 19 |
Correct |
103 ms |
34188 KB |
Output is correct |
| 20 |
Correct |
113 ms |
35744 KB |
Output is correct |
