#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));
return c;
}
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());
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 'void Set(int, int, int, int, int, int)':
trapezoid.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid = l + r >> 1;
| ~~^~~
trapezoid.cpp: In function 'Node Get(int, int, int, int, int)':
trapezoid.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 5 |
Correct |
6 ms |
7636 KB |
Output is correct |
| 6 |
Correct |
9 ms |
7804 KB |
Output is correct |
| 7 |
Correct |
8 ms |
7892 KB |
Output is correct |
| 8 |
Correct |
10 ms |
8020 KB |
Output is correct |
| 9 |
Correct |
23 ms |
8720 KB |
Output is correct |
| 10 |
Correct |
28 ms |
10124 KB |
Output is correct |
| 11 |
Correct |
40 ms |
10860 KB |
Output is correct |
| 12 |
Correct |
84 ms |
14396 KB |
Output is correct |
| 13 |
Correct |
107 ms |
15752 KB |
Output is correct |
| 14 |
Correct |
125 ms |
17144 KB |
Output is correct |
| 15 |
Correct |
168 ms |
17900 KB |
Output is correct |
| 16 |
Correct |
169 ms |
18576 KB |
Output is correct |
| 17 |
Correct |
161 ms |
19316 KB |
Output is correct |
| 18 |
Correct |
129 ms |
20048 KB |
Output is correct |
| 19 |
Correct |
172 ms |
20684 KB |
Output is correct |
| 20 |
Correct |
197 ms |
21412 KB |
Output is correct |
