// from duckindog wth depression
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10,
M = 30013;
struct rec {
int a = 0, b = 0, c = 0, d = 0;
bool operator < (const rec& rhs) {
return make_pair(b, d) < make_pair(rhs.b, rhs.b);
}
} r[N];
int n;
bool crossed(rec x, rec y) {
if (min(x.a, x.c) > min(y.a, y.c)) swap(x, y);
return (x.b >= y.a || x.d >= y.c);
}
vector<int> remind[N];
vector<int> rrh;
using pii = pair<int, int>;
pair<int, int> f[4 * N];
void update(int s, int l, int r, pii x, int y) {
if (y < l || y > r) return;
if (l == r) {
f[s] = max(f[s], x);
return;
}
int mid = l + r >> 1;
update(s * 2, l, mid, x, y); update(s * 2 + 1, mid + 1, r, x, y);
int ma = max(f[s * 2].first, f[s * 2 + 1].first);
f[s].first = ma;
f[s].second = (f[s * 2].second * (f[s * 2].first == ma) + f[s * 2 + 1].second * (f[s * 2 + 1].first == ma)) % M;
}
pii query(int s, int l, int r, int u, int v) {
if (v < l || u > r) return {0, 0};
if (u <= l && r <= v) return f[s];
int mid = l + r >> 1;
auto lt = query(s * 2, l, mid, u, v), rt = query(s * 2 + 1, mid + 1, r, u, v);
int ma = max(lt.first, rt.first);
return {ma, (lt.second * (lt.first == ma) + rt.second * (rt.first == ma)) % M};
}
pii dp[N];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
if (fopen("duck.inp", "r")) {
freopen("duck.inp", "r", stdin);
freopen("duck.out", "w", stdout);
}
cin >> n;
for (int i = 1; i <= n; ++i) {
int a, b, c, d; cin >> a >> b >> c >> d;
r[i] = {a, b, c, d};
rrh.push_back(c), rrh.push_back(d);
}
sort(rrh.begin(), rrh.end());
map<int, int> rvs;
for (int i = 0; i < rrh.size(); ++i) rvs[rrh[i]] = i + 1;
int sz = rrh.size();
sort(r + 1, r + n + 1);
for (int i = 1; i <= n; ++i) {
int a = r[i].a, b = r[i].b;
int lt = 0, rt = i - 1, it = 0;
while (lt <= rt) {
int mid = lt + rt >> 1;
if (r[mid].b <= a) lt = (it = mid) + 1;
else rt = mid - 1;
}
remind[it].push_back(i);
}
dp[0] = {0, 1};
for (int i = 0; i <= n; ++i) {
update(1, 0, sz, dp[i], rvs[r[i].d]);
for (auto x : remind[i]) {
int c = r[x].c, d = r[x].d;
dp[x] = query(1, 0, sz, 0, rvs[c]);
dp[x].first += 1;
}
}
auto answer = query(1, 0, sz, 0, sz);
cout << answer.first << ' ' << answer.second;
}
Compilation message
trapezoid.cpp: In function 'void update(long long int, long long int, long long int, pii, long long int)':
trapezoid.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int mid = l + r >> 1;
| ~~^~~
trapezoid.cpp: In function 'pii query(long long int, long long int, long long int, long long int, long long int)':
trapezoid.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | int mid = l + r >> 1;
| ~~^~~
trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:67:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i = 0; i < rrh.size(); ++i) rvs[rrh[i]] = i + 1;
| ~~^~~~~~~~~~~~
trapezoid.cpp:76:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int mid = lt + rt >> 1;
| ~~~^~~~
trapezoid.cpp:73:21: warning: unused variable 'b' [-Wunused-variable]
73 | int a = r[i].a, b = r[i].b;
| ^
trapezoid.cpp:90:23: warning: unused variable 'd' [-Wunused-variable]
90 | int c = r[x].c, d = r[x].d;
| ^
trapezoid.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | freopen("duck.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | freopen("duck.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
24920 KB |
Output is correct |
| 2 |
Correct |
7 ms |
25176 KB |
Output is correct |
| 3 |
Correct |
8 ms |
25432 KB |
Output is correct |
| 4 |
Correct |
8 ms |
25280 KB |
Output is correct |
| 5 |
Correct |
11 ms |
25436 KB |
Output is correct |
| 6 |
Correct |
11 ms |
25876 KB |
Output is correct |
| 7 |
Correct |
13 ms |
25948 KB |
Output is correct |
| 8 |
Correct |
15 ms |
26460 KB |
Output is correct |
| 9 |
Correct |
22 ms |
27612 KB |
Output is correct |
| 10 |
Correct |
35 ms |
33500 KB |
Output is correct |
| 11 |
Correct |
55 ms |
34004 KB |
Output is correct |
| 12 |
Correct |
96 ms |
42232 KB |
Output is correct |
| 13 |
Correct |
130 ms |
44008 KB |
Output is correct |
| 14 |
Correct |
150 ms |
49240 KB |
Output is correct |
| 15 |
Correct |
190 ms |
50460 KB |
Output is correct |
| 16 |
Correct |
207 ms |
51272 KB |
Output is correct |
| 17 |
Correct |
188 ms |
51908 KB |
Output is correct |
| 18 |
Correct |
154 ms |
52312 KB |
Output is correct |
| 19 |
Correct |
216 ms |
51984 KB |
Output is correct |
| 20 |
Correct |
209 ms |
55968 KB |
Output is correct |
