// from duckindog wth depression
#include<bits/stdc++.h>
using namespace std;
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;
int f[4 * N];
void update(int s, int l, int r, int 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);
f[s] = max(f[s * 2], f[s * 2 + 1]);
}
int query(int s, int l, int r, int u, int v) {
if (v < l || u > r) return 0;
if (u <= l && r <= v) return f[s];
int mid = l + r >> 1;
return max(query(s * 2, l, mid, u, v), query(s * 2 + 1, mid + 1, r, u, v));
}
int 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);
}
for (int i = 0; i <= n; ++i) {
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, 1, 1e6, 1, c) + 1;
}
update(1, 1, 1e6, dp[i], r[i].d);
}
cout << *max_element(dp + 1, dp + n + 1);
}
Compilation message
trapezoid.cpp: In function 'void update(int, int, int, int, int)':
trapezoid.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | int mid = l + r >> 1;
| ~~^~~
trapezoid.cpp: In function 'int query(int, int, int, int, int)':
trapezoid.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int mid = l + r >> 1;
| ~~^~~
trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:61:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid = lt + rt >> 1;
| ~~~^~~~
trapezoid.cpp:58:21: warning: unused variable 'b' [-Wunused-variable]
58 | int a = r[i].a, b = r[i].b;
| ^
trapezoid.cpp:71:11: warning: unused variable 'a' [-Wunused-variable]
71 | int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
| ^
trapezoid.cpp:71:23: warning: unused variable 'b' [-Wunused-variable]
71 | int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
| ^
trapezoid.cpp:71:47: warning: unused variable 'd' [-Wunused-variable]
71 | int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
| ^
trapezoid.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | freopen("duck.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | freopen("duck.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
24924 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
8 ms |
24924 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
9 ms |
25176 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
9 ms |
25180 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
11 ms |
25180 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
10 ms |
25948 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
14 ms |
25616 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
12 ms |
25436 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
16 ms |
25692 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
25 ms |
30548 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
36 ms |
30072 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
50 ms |
34772 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
66 ms |
37200 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
63 ms |
39356 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
74 ms |
34656 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
73 ms |
35960 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
82 ms |
39504 KB |
Unexpected end of file - int32 expected |
| 18 |
Incorrect |
77 ms |
35668 KB |
Unexpected end of file - int32 expected |
| 19 |
Incorrect |
79 ms |
37204 KB |
Unexpected end of file - int32 expected |
| 20 |
Incorrect |
122 ms |
37456 KB |
Unexpected end of file - int32 expected |
