#include <bits/stdc++.h>
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
const int mod = 30013;
class SegmentTree {
private:
vector<int> tree; int n;
int bound = 0;
int merge(int a, int b) {
return max(a, b);
}
void update(int i, int val, int l, int r, int p) {
if (l > i or r < i) return;
if (l == r) {
tree[p] = val;
return;
}
int mid = (l + r) / 2;
int c1 = 2*p+1, c2 = 2*p+2;
update(i, val, l, mid, c1); update(i, val, mid+1, r, c2);
tree[p] = merge(tree[c1], tree[c2]);
}
int mx(int i, int j, int l, int r, int p) {
if (l > j or r < i) return bound;
if (l >= i and r <= j) return tree[p];
int mid = (l + r) / 2;
int c1 = 2*p+1, c2 = 2*p+2;
return merge(mx(i, j, l, mid, c1), mx(i, j, mid+1, r, c2));
}
public:
SegmentTree(int N) {
n = N;
tree.resize(4*n);
}
int mx(int i, int j) {
return mx(i, j, 0, n-1, 0);
}
void update(int i, int val) {
update(i, val, 0, n-1, 0);
}
};
// Ask for sum 1 -> n for full (one based indexing)
class BIT {
private: vector<ll> tree; int n;
int LSOne(int x) {
return x&(-x);
}
public:
BIT(int x) {
n = x;
tree.resize(n+1);
}
ll sum(int a) {
ll sum = 0;
for (; a > 0; a -= LSOne(a)) {
sum += tree[a];
if (sum >= mod) sum -= mod;
if (sum < 0) sum += mod;
}
return sum;
}
ll sum(int a, int b) {
ll ans = sum(b) - (a == 1 ? 0 : sum(a-1));
if (ans >= mod) ans -= mod;
if (ans < 0) ans += mod;
return ans;
}
void update(int p, ll v) {
for (; p < n+1; p += LSOne(p)) {
tree[p] += v;
if (tree[p] >= mod) tree[p] -= mod;
if (tree[p] < 0) tree[p] += mod;
}
}
};
int main() {
#ifdef shiven
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
vector<vi> pts(4*n, vi(2)), lines(2*n);
vi raw(4*n);
int lpt = 0;
for_(i, 0, n) {
for_(j, 4*i, 4*i+4) {
cin >> pts[j][0];
pts[j][1] = j;
}
}
sort(pts.begin(), pts.end());
int last = 0;
for_(i, 0, pts.size()) {
if (i == 0 or pts[i-1][0] != pts[i][0]) {
raw[pts[i][1]] = i;
last = i;
} else raw[pts[i][1]] = last;
}
for_(i, 0, n) {
lines[lpt++] = {raw[4*i], raw[4*i+2], i}; lines[lpt++] = {raw[4*i+1], raw[4*i+3], i};
}
sort(lines.begin(), lines.end());
SegmentTree tree(last+1);
vi v(n, -1), ct(n+1, -1);
ct[n] = 1;
vector<vector<vi>> withLenIn(n+1), withLenOut(n+1);
withLenOut[0].push_back({-1, 0, n});
lpt = 0;
for (auto i: lines) {
if (v[i[2]] == -1) {
v[i[2]] = tree.mx(0, i[1]) + 1;
//cout << i[2]+1 << " " << i[1] << " -> " << v[i[2]] << endl;
withLenIn[v[i[2]]].push_back({lpt++, i[1], i[2]});
}
else {
tree.update(i[1], v[i[2]]);
withLenOut[v[i[2]]].push_back({lpt++, i[1], i[2]});
}
}
BIT fenwick(last+1);
int l = 0, count = 0;
for_(i, 1, n+1) {
if (!withLenIn[i].size()) break;
//if (i == 1) {
//for (auto t: withLenIn[i]) ct[t[2]] = 1;
//continue;
//}
//cout << "on " << i << endl;
l = i; count = 0;
int pt = 0;
for (auto t: withLenIn[i]) {
while (pt < withLenOut[i-1].size() and withLenOut[i-1][pt][0] < t[0]) {
fenwick.update(withLenOut[i-1][pt][1]+1, ct[withLenOut[i-1][pt][2]]);
pt++;
}
ct[t[2]] = fenwick.sum(t[1]+1);
//cout << t[2] << " gets " << ct[t[2]] << endl;
count += ct[t[2]];
if (count >= mod) count -= mod;
}
for (pt = min(pt, (int) withLenOut[i-1].size())-1; pt >= 0; pt--) fenwick.update(withLenOut[i-1][pt][1]+1, -ct[withLenOut[i-1][pt][2]]);
}
cout << l << " " << count << endl;
return 0;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:161:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | while (pt < withLenOut[i-1].size() and withLenOut[i-1][pt][0] < t[0]) {
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
640 KB |
Output is correct |
4 |
Correct |
3 ms |
1024 KB |
Output is correct |
5 |
Correct |
5 ms |
1664 KB |
Output is correct |
6 |
Correct |
7 ms |
2304 KB |
Output is correct |
7 |
Correct |
10 ms |
2944 KB |
Output is correct |
8 |
Correct |
13 ms |
3456 KB |
Output is correct |
9 |
Correct |
27 ms |
6648 KB |
Output is correct |
10 |
Correct |
56 ms |
13320 KB |
Output is correct |
11 |
Correct |
71 ms |
16504 KB |
Output is correct |
12 |
Correct |
170 ms |
32248 KB |
Output is correct |
13 |
Correct |
209 ms |
38560 KB |
Output is correct |
14 |
Correct |
250 ms |
45048 KB |
Output is correct |
15 |
Correct |
282 ms |
47864 KB |
Output is correct |
16 |
Correct |
328 ms |
50936 KB |
Output is correct |
17 |
Correct |
301 ms |
54392 KB |
Output is correct |
18 |
Correct |
269 ms |
57720 KB |
Output is correct |
19 |
Correct |
326 ms |
60472 KB |
Output is correct |
20 |
Correct |
363 ms |
63600 KB |
Output is correct |