/**
* author : Lăng Trọng Đạt
* created: 16-10-2024
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define int long long
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a); (i) <= (b); (i++))
#define FD(i, lo, up) for (int i = (up); (i) >= (lo); i--)
#define si(x) (int)(x.size())
bool mx(int& a, int b) { if (b > a) {a = b; return true;} return false;}
bool mi(int& a, int b) { if (b < a) {a = b; return true;} return false;}
using pii = pair<int, int>;
const int INF = 1e18 + 5;
const int MOD = 1e9 + 7;
const int N = 1e6 + 5;
int g[N];
int n, m, k, q, a, b, c, d;
vector<int> vals = {-1, MOD};
struct Data
{
vector<int> v;
} t[N];
int res[N];
int bit_max[4*N];
void upd_max(int p, int val) {
for (; p <= si(vals); p += p & -p)
mx(bit_max[p], val);
}
int get_max(int p) {
int res = 0;
for (; p > 0; p -= p & -p)
mx(res, bit_max[p]);
return res;
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
if (fopen("hi.inp", "r")) {
freopen("hi.inp", "r", stdin);
// freopen("hi.out", "w", stdout);
}
cin >> n;
vector<array<int, 3>> events;
FOR(i, 1, n) {
t[i].v.resize(4);
for (int& j : t[i].v) {
cin >> j;
vals.push_back(j);
}
// cin >> t[i].a >> t[i].b >> t[i].c >> t[i].d;
// vals.push_back(t[i].a); vals.push_back(t[i].b); vals.push_back(t[i].c); vals.push_back(t[i].d);
events.push_back({t[i].v[0], 0, i});
events.push_back({t[i].v[1], 1, i});
}
sort(all(events));
sort(all(vals));
vals.resize(unique(all(vals)) - vals.begin());
for(auto[x, type, ind] : events) {
vector<int> v = t[ind].v;
for (int& i : v) {
i = lower_bound(all(vals), i) - vals.begin();
}
db(x, v[2], v[3])
if (type == 0) {
res[ind] = get_max(v[2]) + 1;
} else {
upd_max(v[3], res[ind]);
}
}
cout << get_max(si(vals)) << " ";
}
Compilation message
trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:75:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
75 | for(auto[x, type, ind] : events) {
| ^
trapezoid.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | freopen("hi.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
29008 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
5 ms |
29008 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
5 ms |
29264 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
7 ms |
29264 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
8 ms |
29536 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
9 ms |
29776 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
9 ms |
29972 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
13 ms |
29964 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
18 ms |
30688 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
30 ms |
32548 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
43 ms |
33556 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
84 ms |
38248 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
100 ms |
40040 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
120 ms |
44448 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
133 ms |
44376 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
159 ms |
45064 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
148 ms |
45912 KB |
Unexpected end of file - int32 expected |
| 18 |
Incorrect |
126 ms |
47448 KB |
Unexpected end of file - int32 expected |
| 19 |
Incorrect |
147 ms |
48468 KB |
Unexpected end of file - int32 expected |
| 20 |
Incorrect |
177 ms |
48984 KB |
Unexpected end of file - int32 expected |
