/**
* 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 = 30013;
void add(int& a, int b) {
a = (a + b) % MOD;
}
const int N = 1e5 + 5;
int g[N];
int n, m, k, q, a, b, c, d;
vector<int> vals = {-1, 0, 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)
add(bit_cnt[p], val);
}
int get_cnt(int p) {
int res = 0;
for (; p > 0; p -= p & -p)
add(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) add(cnt_max, cnt[i]);
}
cout << ans << " " << cnt_max;
}
Compilation message
trapezoid.cpp:22:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
22 | const int INF = 1e18 + 5;
| ~~~~~^~~
trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:91:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
91 | for(auto[x, type, ind] : events) {
| ^
trapezoid.cpp:108:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
108 | for (auto[type, ind] : group[i]) {
| ^
trapezoid.cpp:124:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
124 | for (auto[type, ind] : group[i]) {
| ^
trapezoid.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | freopen("hi.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9040 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9040 KB |
Output is correct |
| 3 |
Correct |
3 ms |
9040 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9040 KB |
Output is correct |
| 5 |
Correct |
7 ms |
9296 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9296 KB |
Output is correct |
| 7 |
Correct |
12 ms |
9552 KB |
Output is correct |
| 8 |
Correct |
19 ms |
9552 KB |
Output is correct |
| 9 |
Correct |
36 ms |
10204 KB |
Output is correct |
| 10 |
Correct |
55 ms |
11268 KB |
Output is correct |
| 11 |
Correct |
102 ms |
11904 KB |
Output is correct |
| 12 |
Correct |
203 ms |
14384 KB |
Output is correct |
| 13 |
Correct |
248 ms |
15476 KB |
Output is correct |
| 14 |
Correct |
308 ms |
16920 KB |
Output is correct |
| 15 |
Correct |
359 ms |
17340 KB |
Output is correct |
| 16 |
Correct |
402 ms |
17896 KB |
Output is correct |
| 17 |
Correct |
412 ms |
18236 KB |
Output is correct |
| 18 |
Correct |
319 ms |
18792 KB |
Output is correct |
| 19 |
Correct |
451 ms |
19468 KB |
Output is correct |
| 20 |
Correct |
453 ms |
20212 KB |
Output is correct |
