#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5;
const int MOD = 30013;
int n;
pii left_edge[MAXN];
pii right_edge[MAXN];
map<int, int> convert;
vector<int> top_coords;
class stree {
public:
stree *l = nullptr;
stree *r = nullptr;
int lp, rp;
pii opt; // max, ways_to_achieve
stree(int lv, int rv) {
opt = pii(0, 0);
lp = lv;
rp = rv;
if (lp != rp) {
int m = (lp+rp)/2;
l = new stree(lp, m);
r = new stree(m+1, rp);
}
}
pii comb(pii a, pii b) {
if (a.first == b.first) return pii(a.first, (a.second+b.second) % MOD);
return max(a, b);
}
void comb() {
opt = comb(l->opt, r->opt);
}
void update(int p, pii v) {
if (lp > p || rp < p) return;
if (lp == rp) {
opt = v;
return;
}
l->update(p, v);
r->update(p, v);
comb();
}
pii query(int lv, int rv) {
if (lp > rv || rp < lv) return pii(0, 0);
if (lp >= lv && rp <= rv) return opt;
return comb(l->query(lv, rv), r->query(lv, rv));
}
};
class edge {
public:
int b_point;
int t_point;
int id;
int l_or_r; // l is 1, r is 0
edge() {}
edge(int b, int t, int i, int lr) : b_point(b), t_point(t), id(i), l_or_r(lr) {}
};
bool operator<(edge &a, edge &b) {
return (a.b_point > b.b_point);
}
edge edges[2*MAXN];
pii dp_query[MAXN];
stree *tree;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
int a, b, c, d; cin >> a >> b >> c >> d;
left_edge[i] = pii(a, c);
right_edge[i] = pii(b, d);
top_coords.push_back(a);
top_coords.push_back(b);
}
sort(top_coords.begin(), top_coords.end());
for (int t = 0; t < top_coords.size(); t++) convert[top_coords[t]] = t;
for (int i = 0; i < n; i++) {
left_edge[i].first = convert[left_edge[i].first];
right_edge[i].first = convert[right_edge[i].first];
edges[2*i] = edge(left_edge[i].second, left_edge[i].first, i, 1);
edges[2*i+1] = edge(right_edge[i].second, right_edge[i].first, i, 0);
}
sort(edges, edges+2*n);
tree = new stree(0, 2*n);
tree->update(2*n, pii(0, 1));
for (int i = 0; i < 2*n; i++) {
if (edges[i].l_or_r) tree->update(edges[i].t_point, dp_query[edges[i].id]);
else {
dp_query[edges[i].id] = tree->query(edges[i].t_point+1, 2*n);
dp_query[edges[i].id].first++;
}
}
pii ans = tree->query(0, 2*n);
cout << ans.first << " " << ans.second << "\n";
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int t = 0; t < top_coords.size(); t++) convert[top_coords[t]] = t;
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
2 ms |
612 KB |
Output is correct |
| 5 |
Correct |
3 ms |
980 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1364 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1756 KB |
Output is correct |
| 8 |
Correct |
9 ms |
2188 KB |
Output is correct |
| 9 |
Correct |
21 ms |
4000 KB |
Output is correct |
| 10 |
Correct |
32 ms |
7760 KB |
Output is correct |
| 11 |
Correct |
44 ms |
9584 KB |
Output is correct |
| 12 |
Correct |
96 ms |
18928 KB |
Output is correct |
| 13 |
Correct |
141 ms |
22508 KB |
Output is correct |
| 14 |
Correct |
138 ms |
26364 KB |
Output is correct |
| 15 |
Correct |
148 ms |
28072 KB |
Output is correct |
| 16 |
Correct |
186 ms |
29916 KB |
Output is correct |
| 17 |
Correct |
166 ms |
31944 KB |
Output is correct |
| 18 |
Correct |
147 ms |
33672 KB |
Output is correct |
| 19 |
Correct |
183 ms |
35616 KB |
Output is correct |
| 20 |
Correct |
197 ms |
37448 KB |
Output is correct |
