#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(v) (int)(v).size()
using namespace std;
const int MAXn = 100005, MOD = 30013;
void add(int &X, int Y) {
if ((X += Y) >= MOD) X -= MOD;
}
struct sth {
int a, b, c, d;
} h[MAXn];
int n, k;
int val[(1 << 19) + 5], cnt[(1 << 19) + 5];
void update(int i, int v, int c) {
int id = 1, l = -1, r = 2 * n;
while (l < r) {
int mid = (l + r) >> 1;
if (i <= mid) {
r = mid;
id <<= 1;
} else {
l = mid + 1;
id = id << 1 | 1;
}
}
if (val[id] < v) {
val[id] = v;
cnt[id] = c;
} else if (val[id] == v) add(cnt[id], c);
while (id > 1) {
id >>= 1;
int Lv = val[id << 1], Rv = val[id << 1 | 1];
val[id] = max(Lv, Rv);
if (Lv < Rv) cnt[id] = cnt[id << 1 | 1];
else if (Lv > Rv) cnt[id] = cnt[id << 1];
else {
cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
if (cnt[id] >= MOD) cnt[id] -= MOD;
}
}
}
pair<int, int> get(int Rt) {
int v = -1, c = 0;
int id = 1, l = -1, r = 2 * n;
while (l < r) {
int mid = (l + r) >> 1;
if (Rt <= mid) {
r = mid;
id <<= 1;
} else {
if (v < val[id << 1]) c = cnt[id << 1];
else if (v == val[id << 1]) add(c, cnt[id << 1]);
v = max(v, val[id << 1]);
l = mid + 1;
id = id << 1 | 1;
}
}
if (v < val[id]) c = cnt[id];
else if (v == val[id]) add(c, cnt[id]);
v = max(v, val[id]);
return {v, c};
}
struct state {
int t, x, id;
};
vector<state> vct;
int dp[MAXn], f[MAXn];
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
#define TASK "TRAPEZ"
if (ifstream(TASK".INP")) {
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
cin >> n;
vector<int> ne2;
for (int i = 1, a, b, c, d; i <= n; i++) {
cin >> a >> b >> c >> d;
h[i] = {a, b, c, d};
ne2.emplace_back(c);
ne2.emplace_back(d);
vct.push_back({0, a, i});
vct.push_back({1, b, i});
}
sort(begin(ne2), end(ne2));
ne2.resize(unique(begin(ne2), end(ne2)) - ne2.begin());
for (int i = 1; i <= n; i++) {
h[i].c = lower_bound(begin(ne2), end(ne2), h[i].c) - ne2.begin();
h[i].d = lower_bound(begin(ne2), end(ne2), h[i].d) - ne2.begin();
}
sort(begin(vct), end(vct), [&] (const state &X, const state &Y) {
return X.x < Y.x;
});
memset(val, -1, sizeof val);
for (int i = 0; i < sz(ne2); i++) update(i, -1, 0);
update(-1, 0, 1);
for (auto tt: vct) {
int id = tt.id;
if (!tt.t) {
pair<int, int> tmp = get(h[id].c - 1);
dp[id] = tmp.fi + 1;
f[id] = tmp.se;
} else {
update(h[id].d, dp[id], f[id]);
}
}
int ans1 = 0, ans2 = 0;
for (int i = 1; i <= n; i++) {
if (ans1 < dp[i]) {
ans1 = dp[i];
ans2 = f[i];
} else if (ans1 == dp[i]) add(ans2, f[i]);
}
cout << ans1 << ' ' << ans2;
return 0;
}
// Revive! >:)
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:78:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:79:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | freopen(TASK".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6844 KB |
Output is correct |
| 8 |
Correct |
4 ms |
6944 KB |
Output is correct |
| 9 |
Correct |
8 ms |
7028 KB |
Output is correct |
| 10 |
Correct |
15 ms |
7408 KB |
Output is correct |
| 11 |
Correct |
20 ms |
7612 KB |
Output is correct |
| 12 |
Correct |
42 ms |
8424 KB |
Output is correct |
| 13 |
Correct |
57 ms |
8680 KB |
Output is correct |
| 14 |
Correct |
59 ms |
9168 KB |
Output is correct |
| 15 |
Correct |
64 ms |
9940 KB |
Output is correct |
| 16 |
Correct |
72 ms |
9424 KB |
Output is correct |
| 17 |
Correct |
74 ms |
9428 KB |
Output is correct |
| 18 |
Correct |
70 ms |
9972 KB |
Output is correct |
| 19 |
Correct |
74 ms |
9836 KB |
Output is correct |
| 20 |
Correct |
85 ms |
10188 KB |
Output is correct |
