#include <bits/stdc++.h>
using namespace std;
// one trapezium doesn't overlap with another if and only if a2>b1 and c2>d1
// so at each 'b', add the LIS value on the bottom line 'd'
// and at each 'd', add the LIS value on the top line at 'b'
// then at each 'a', range query the bottom in [1, c-1] and add 1
// and at each 'c', range query for all top in [1, a-1] and add 1
// what about when b < c ?, when updating the LIS, update
// any values on the top/bottom lines too, if they exist
const int mod = 30013;
struct Info {
int m, ct;
Info(int M, int C) : m(M), ct(C%mod) {}
Info() : Info(0, 0) {}
Info combine(Info &other) {
if (m == other.m) return {m, ct + other.ct};
else if (m > other.m) return {m, ct};
else return {other.m, other.ct};
}
};
struct Tree {
vector<Info> info;
Tree(int size) { info.resize(size*4); }
void update(int v, int x, int xl, int xr, Info delta) {
if (xl == xr) {
info[x] = delta;
} else {
int xm = (xl + xr) / 2;
if (v <= xm) update(v, x*2, xl, xm, delta);
else update(v, x*2+1, xm+1, xr, delta);
info[x] = info[x*2].combine(info[x*2+1]);
}
}
Info query(int l, int r, int x, int xl, int xr) {
if (l > r) return {};
assert(xl <= xr);
if (l == xl && r == xr) {
return info[x];
} else {
int xm = (xl + xr) / 2;
Info left = query(l, min(r, xm), x*2, xl, xm);
Info right = query(max(l, xm+1), r, x*2+1, xm+1, xr);
return left.combine(right);
}
}
};
int main() {
// take inputs // coord compression
cin.tie(0)->sync_with_stdio(0);
int N;
cin >> N;
vector<array<int,4>> shapes(N);
set<int> coords;
for (int i=0; i<N; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
coords.insert(a); coords.insert(c);
coords.insert(b); coords.insert(d);
shapes[i] = {{a, b, c, d}};
}
map<int,int> idxmap;
int L = 0;
for (int coord : coords) idxmap[coord] = L++;
// find events
vector<array<int,5>> events;
for (int i=0; i<N; i++) {
array<int,4> shape = shapes[i];
events.push_back({shape[0], i, 0, 1, idxmap[shape[2]]-1}); // 0=query,1=bottom
events.push_back({shape[2], i, 0, 0, idxmap[shape[0]]-1}); // 0=query,0=top
events.push_back({shape[1], i, 1, 1, idxmap[shape[3]]}); // 1=update,1=bottom
events.push_back({shape[3], i, 1, 0, idxmap[shape[1]]}); // 1=update,0=top
}
sort(events.begin(), events.end());
// make trees and sweep line
vector<Info> lisValue(N, {1, 1});
Tree topTree(L), bottomTree(L);
vector<int> topPos(N, -1), bottomPos(N, -1);
for (array<int,5> event : events) {
if (event[2] == 0) {
// query
Info info;
if (event[3] == 0) info = topTree.query(0, event[4], 1, 0, L-1);
else info = bottomTree.query(0, event[4], 1, 0, L-1);
info.m += 1;
if (info.m == 1) info.ct = 1; // can only start once
lisValue[event[1]] = info;
} else {
// update
if (event[3] == 0) topPos[event[1]] = event[4];
else bottomPos[event[1]] = event[4];
}
if (topPos[event[1]] != -1) {
topTree.update(topPos[event[1]], 1, 0, L-1, lisValue[event[1]]);
}
if (bottomPos[event[1]] != -1) {
bottomTree.update(bottomPos[event[1]], 1, 0, L-1, lisValue[event[1]]);
}
// cout << "---\n";
// for (int i=0; i<L; i++) cout << topTree.query(i, i, 1, 0, L-1).m << " "; cout << "\n";
// for (int i=0; i<L; i++) cout << bottomTree.query(i, i, 1, 0, L-1).m << " "; cout << "\n";
}
// get overall answer
Info all = topTree.query(0, L-1, 1, 0, L-1);
cout << all.m << " " << all.ct << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
2 ms |
860 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1852 KB |
Output is correct |
| 6 |
Correct |
8 ms |
2456 KB |
Output is correct |
| 7 |
Correct |
8 ms |
2200 KB |
Output is correct |
| 8 |
Correct |
18 ms |
3364 KB |
Output is correct |
| 9 |
Correct |
32 ms |
7372 KB |
Output is correct |
| 10 |
Correct |
45 ms |
8664 KB |
Output is correct |
| 11 |
Correct |
90 ms |
17860 KB |
Output is correct |
| 12 |
Correct |
190 ms |
35512 KB |
Output is correct |
| 13 |
Correct |
232 ms |
40880 KB |
Output is correct |
| 14 |
Correct |
293 ms |
50956 KB |
Output is correct |
| 15 |
Correct |
314 ms |
45760 KB |
Output is correct |
| 16 |
Correct |
352 ms |
49036 KB |
Output is correct |
| 17 |
Correct |
375 ms |
58532 KB |
Output is correct |
| 18 |
Correct |
232 ms |
39008 KB |
Output is correct |
| 19 |
Correct |
372 ms |
62384 KB |
Output is correct |
| 20 |
Correct |
431 ms |
65536 KB |
Output is correct |
