#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int mod = 30013;
int Add(int a, int b) {
a += b;
if (a >= mod) a -= mod;
return a;
}
struct Node {
int x, y;
Node() {
x = y = 0;
}
Node(int a, int b) {
x = a; y = b;
}
};
Node Merge(Node a, Node b) {
Node c;
if (a.x > b.x) c = a;
else if (a.x < b.x) c = b;
else c = Node(a.x, Add(a.y, b.y));
}
Node st[8 * N];
void Set(int node, int l, int r, int p, int x, int y) {
if (l == r) {
st[node] = Node(x, y);
return;
}
int mid = l + r >> 1;
if (p <= mid) Set(2 * node, l, mid, p, x, y);
else Set(2 * node + 1, mid + 1, r, p, x, y);
st[node] = Merge(st[2 * node], st[2 * node + 1]);
}
Node Get(int node, int l, int r, int ql, int qr) {
if (r < ql || qr < l) return Node();
if (ql <= l && r <= qr) return st[node];
int mid = l + r >> 1;
return Merge(Get(2 * node, l, mid, ql, qr), Get(2 * node + 1, mid + 1, r, ql, qr));
}
Node ans[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n; cin >> n;
vector<int> a(n), b(n), c(n), d(n);
vector<array<int, 3>> all;
vector<int> v;
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
all.push_back({a[i], i, 0});
all.push_back({b[i], i, 1});
v.push_back(c[i]); v.push_back(d[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
sort(all.begin(), all.end());
map<int, int> mp;
int x = 0;
for (int i : v) mp[i] = x++;
for (auto u : all) {
if (u[2] == 0) {
ans[u[1]] = Get(1, 0, x - 1, 0, mp[c[u[1]]]);
ans[u[1]].x += 1;
if (ans[u[1]].x == 1) ans[u[1]].y += 1;
}
else Set(1, 0, x - 1, mp[d[u[1]]], ans[u[1]].x, ans[u[1]].y);
}
int mx = 0;
for (int i = 0; i < n; i++) smax(mx, ans[i].x);
int sol = 0;
for (int i = 0; i < n; i++) if (ans[i].x == mx) sol = Add(sol, ans[i].y);
cout << mx << sp << sol << en;
return 0;
}
Compilation message
trapezoid.cpp: In function 'Node Merge(Node, Node)':
trapezoid.cpp:30:1: warning: no return statement in function returning non-void [-Wreturn-type]
30 | }
| ^
trapezoid.cpp: In function 'void Set(int, int, int, int, int, int)':
trapezoid.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int mid = l + r >> 1;
| ~~^~~
trapezoid.cpp: In function 'Node Get(int, int, int, int, int)':
trapezoid.cpp:45:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
14676 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
12 ms |
14676 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
11 ms |
14932 KB |
Execution killed with signal 6 |
| 4 |
Runtime error |
13 ms |
15060 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
14 ms |
15220 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
13 ms |
15656 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
14 ms |
15812 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
15 ms |
16212 KB |
Execution killed with signal 6 |
| 9 |
Runtime error |
24 ms |
17544 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
28 ms |
20476 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
33 ms |
21796 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
59 ms |
29076 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
69 ms |
31892 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
82 ms |
34744 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
87 ms |
36132 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
100 ms |
37640 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
116 ms |
39060 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
108 ms |
40444 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
106 ms |
41872 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
136 ms |
43280 KB |
Execution killed with signal 11 |
