// 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};
}
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, 1e6, dp[i], r[i].d);
for (auto x : remind[i]) {
int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
dp[x] = query(1, 0, 1e6, 0, c);
dp[x].first += 1;
}
}
auto answer = query(1, 0, 1e6, 0, 1e6);
cout << answer.first << ' ' << answer.second % M;
}
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:69:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int mid = lt + rt >> 1;
| ~~~^~~~
trapezoid.cpp:66:21: warning: unused variable 'b' [-Wunused-variable]
66 | int a = r[i].a, b = r[i].b;
| ^
trapezoid.cpp:84:11: warning: unused variable 'a' [-Wunused-variable]
84 | int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
| ^
trapezoid.cpp:84:23: warning: unused variable 'b' [-Wunused-variable]
84 | int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
| ^
trapezoid.cpp:84:47: warning: unused variable 'd' [-Wunused-variable]
84 | int a = r[x].a, b = r[x].b, 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 |
9 ms |
33116 KB |
Output is correct |
| 2 |
Correct |
9 ms |
33116 KB |
Output is correct |
| 3 |
Correct |
10 ms |
33116 KB |
Output is correct |
| 4 |
Correct |
10 ms |
33372 KB |
Output is correct |
| 5 |
Correct |
12 ms |
33628 KB |
Output is correct |
| 6 |
Correct |
14 ms |
34652 KB |
Output is correct |
| 7 |
Correct |
13 ms |
34252 KB |
Output is correct |
| 8 |
Correct |
13 ms |
33628 KB |
Output is correct |
| 9 |
Correct |
18 ms |
33884 KB |
Output is correct |
| 10 |
Correct |
31 ms |
44896 KB |
Output is correct |
| 11 |
Correct |
36 ms |
39752 KB |
Output is correct |
| 12 |
Correct |
64 ms |
51536 KB |
Output is correct |
| 13 |
Correct |
80 ms |
52608 KB |
Output is correct |
| 14 |
Incorrect |
82 ms |
59684 KB |
Output isn't correct |
| 15 |
Correct |
92 ms |
47104 KB |
Output is correct |
| 16 |
Correct |
100 ms |
50472 KB |
Output is correct |
| 17 |
Correct |
121 ms |
60164 KB |
Output is correct |
| 18 |
Correct |
92 ms |
50256 KB |
Output is correct |
| 19 |
Correct |
111 ms |
50424 KB |
Output is correct |
| 20 |
Correct |
119 ms |
54608 KB |
Output is correct |
