/**
* 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 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;
}
int bit_cnt[4*N];
void upd_cnt(int p, int val) {
for (; p <= si(vals); p += p & -p)
bit_cnt[p] += val;
}
int get_cnt(int p) {
int res = 0;
for (; p > 0; p -= p & -p)
res += bit_cnt[p];
return res;
}
int res[N], cnt[N];
vector<pii> group[N];
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);
}
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());
group[1].push_back({1, 0});
cnt[0] = 1;
t[0].v = {0, 0, 0, 0};
for(auto[x, type, ind] : events) {
vector<int> v = t[ind].v;
for (int& i : v) {
i = lower_bound(all(vals), i) - vals.begin();
}
if (type == 0) {
res[ind] = get_max(v[2]) + 1;
} else {
upd_max(v[3], res[ind]);
}
group[res[ind]].push_back({type, ind});
group[res[ind] + 1].push_back({type, ind});
}
int ans = get_max(si(vals));
FOR(i, 1, ans) {
for (auto[type, ind] : group[i]) {
vector<int> v = t[ind].v;
for (int& i : v) {
i = lower_bound(all(vals), i) - vals.begin();
}
if (type == 0) {
if (res[ind] == i) {
cnt[ind] = get_cnt(v[2]);
}
} else {
if (res[ind] == i - 1) {
// db(v[3], ind, cnt[ind])
upd_cnt(v[3], cnt[ind]);
}
}
}
for (auto[type, ind] : group[i]) {
vector<int> v = t[ind].v;
for (int& i : v) {
i = lower_bound(all(vals), i) - vals.begin();
}
if (type == 1) {
if (res[ind] == i - 1) {
upd_cnt(v[3], -cnt[ind]);
}
}
}
}
int cnt_max = 0;
FOR(i, 1, n) {
if (res[i] == ans) cnt_max += cnt[i];
assert(cnt_max >= 0);
}
cout << ans << " " << cnt_max;
}
Compilation message
trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:89:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
89 | for(auto[x, type, ind] : events) {
| ^
trapezoid.cpp:105:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
105 | for (auto[type, ind] : group[i]) {
| ^
trapezoid.cpp:121:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
121 | for (auto[type, ind] : group[i]) {
| ^
trapezoid.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | freopen("hi.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
53840 KB |
Output is correct |
| 2 |
Correct |
12 ms |
53852 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
54120 KB |
Expected int32, but "10313130667392" found |
| 4 |
Runtime error |
128 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Partially correct |
15 ms |
56400 KB |
Partially correct |
| 6 |
Runtime error |
73 ms |
65536 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
66 ms |
65536 KB |
Execution killed with signal 9 |
| 8 |
Partially correct |
28 ms |
56980 KB |
Partially correct |
| 9 |
Incorrect |
47 ms |
58244 KB |
Expected int32, but "2248786528710863832" found |
| 10 |
Runtime error |
110 ms |
65536 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
129 ms |
65536 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
109 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
112 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
75 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
84 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
87 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
84 ms |
65536 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
91 ms |
65536 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
93 ms |
65536 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
87 ms |
65536 KB |
Execution killed with signal 9 |
