#include <bits/stdc++.h>
using namespace std;
struct Rect{
int us, ue;
int ds, de;
bool operator<(const Rect &oth) const {
return ue < oth.ue;
}
}a[100001];
int n;
int ux[200002], dx[200002];
struct Node{
Node *l, *r;
pair<int, int> data;
Node() : l(NULL), r(NULL), data({0, 1}) {}
}*tree[100001];
pair<int, int> merge(pair<int, int> x, pair<int, int> y){
if(x.first == y.first) return {x.first, x.first ? (x.second + y.second) % 30013 : 1};
return max(x, y);
}
void init(Node *cur, int s, int e){
cur->data = {0, 1};
if(s == e) return;
cur->l = new Node();
cur->r = new Node();
init(cur->l, s, (s+e)/2);
init(cur->r, (s+e)/2 + 1, e);
}
Node* make_tree(Node *cur, int s, int e, int x, pair<int, int> v){
if(x < s || e < x) return cur;
Node *ret = new Node();
if(s == e){
ret->data = v;
return ret;
}
ret->l = make_tree(cur->l, s, (s+e)/2, x, v);
ret->r = make_tree(cur->r, (s+e)/2 + 1, e, x, v);
ret->data = merge(ret->l->data, ret->r->data);
return ret;
}
pair<int, int> query(Node *cur, int s, int e, int x, int y){
if(e < x || y < s) return {0, 1};
if(x <= s && e <= y) return cur->data;
return merge(query(cur->l, s, (s+e)/2, x, y),
query(cur->r, (s+e)/2 + 1, e, x, y));
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
int us, ue, ds, de;
scanf("%d%d%d%d", &us, &ue, &ds, &de);
ux[2 * i - 1] = us;
ux[2 * i] = ue;
dx[2 * i - 1] = ds;
dx[2 * i] = de;
a[i] = {us, ue, ds, de};
}
sort(ux + 1, ux + 2 * n + 1);
sort(dx + 1, dx + 2 * n + 1);
for(int i = 1; i <= n; i++){
a[i].us = lower_bound(ux + 1, ux + 2 * n + 1, a[i].us) - ux;
a[i].ue = lower_bound(ux + 1, ux + 2 * n + 1, a[i].ue) - ux;
a[i].ds = lower_bound(dx + 1, dx + 2 * n + 1, a[i].ds) - dx;
a[i].de = lower_bound(dx + 1, dx + 2 * n + 1, a[i].de) - dx;
}
sort(a + 1, a + n + 1);
tree[0] = new Node();
init(tree[0], 1, 2 * n);
for(int i = 1; i <= n; i++){
int t = lower_bound(a + 1, a + n + 1, (Rect){0, a[i].us, 0, 0}) - a - 1;
pair<int, int> x = query(tree[t], 1, 2 * n, 1, a[i].ds);
tree[i] = make_tree(tree[i - 1], 1, 2 * n, a[i].de, {x.first + 1, x.second});
}
printf("%d %d\n", tree[n]->data.first, tree[n]->data.second);
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:56:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
trapezoid.cpp:59:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &us, &ue, &ds, &de);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5928 KB |
Output is correct |
| 2 |
Correct |
0 ms |
5928 KB |
Output is correct |
| 3 |
Correct |
0 ms |
6192 KB |
Output is correct |
| 4 |
Correct |
0 ms |
6456 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6984 KB |
Output is correct |
| 6 |
Correct |
0 ms |
7644 KB |
Output is correct |
| 7 |
Correct |
3 ms |
8172 KB |
Output is correct |
| 8 |
Correct |
9 ms |
8832 KB |
Output is correct |
| 9 |
Correct |
29 ms |
12000 KB |
Output is correct |
| 10 |
Correct |
53 ms |
18732 KB |
Output is correct |
| 11 |
Correct |
79 ms |
22164 KB |
Output is correct |
| 12 |
Correct |
169 ms |
39852 KB |
Output is correct |
| 13 |
Correct |
216 ms |
46980 KB |
Output is correct |
| 14 |
Correct |
269 ms |
54372 KB |
Output is correct |
| 15 |
Correct |
306 ms |
58068 KB |
Output is correct |
| 16 |
Correct |
363 ms |
61896 KB |
Output is correct |
| 17 |
Memory limit exceeded |
313 ms |
65536 KB |
Memory limit exceeded |
| 18 |
Memory limit exceeded |
239 ms |
65536 KB |
Memory limit exceeded |
| 19 |
Memory limit exceeded |
289 ms |
65536 KB |
Memory limit exceeded |
| 20 |
Memory limit exceeded |
329 ms |
65536 KB |
Memory limit exceeded |
