#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }
const int MX = 100 * 1000 + 5;
int bl[MX], br[MX], ul[MX], ur[MX];
vi r2i[2 * MX], l2i[2 * MX];
vi vu, vb;
int otr2dep[MX];
int vu2c(int v) {
return lower_bound(all(vu), v) - vu.begin();
}
int vb2c(int v) {
return lower_bound(all(vb), v) - vb.begin();
}
struct Seg {
int n;
vi mx;
Seg(int n): n(n) {
mx.assign(2 * n, -1);
}
int query(int l, int r) {
int res = -1;
for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) maxeq(res, mx[l++]);
if(r & 1) maxeq(res, mx[--r]);
}
return res;
}
void update(int p, int v) {
for(maxeq(mx[p += n], v); p > 1; p >>= 1) {
mx[p >> 1] = max(mx[p], mx[p ^ 1]);
}
}
};
void solve() {
int n;
cin >> n;
forn(i, n) {
cin >> ul[i] >> ur[i] >> bl[i] >> br[i];
vu.pb(ul[i]);
vu.pb(ur[i]);
vb.pb(bl[i]);
vb.pb(br[i]);
}
sort(all(vu));
sort(all(vb));
vu.erase(unique(all(vu)), vu.end());
vb.erase(unique(all(vb)), vb.end());
forn(i, n) {
ul[i] = vu2c(ul[i]);
ur[i] = vu2c(ur[i]);
bl[i] = vb2c(bl[i]);
br[i] = vb2c(br[i]);
r2i[br[i]].pb(i);
l2i[bl[i]].pb(i);
}
Seg seg(sz(vu));
forn(botc, sz(vb)) {
for(int i: l2i[botc]) {
int depth = seg.query(0, ul[i] - 1) + 1;
otr2dep[i] = depth;
// if(i == 5)
// forn(w, sz(vu)) {
// cout << "pos " << w << ", value " << seg.query(w, w) << '\n';
// }
cout << i + 1 << ' ' << depth << '\n';
}
for(int i: r2i[botc]) {
seg.update(ur[i], otr2dep[i]);
// cout << "processed " << i + 1 << '\n';
}
}
int mxd = 0;
forn(i, n)
maxeq(mxd, otr2dep[i]);
cout << mxd + 1 << ' ' << 0 << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// freopen("slingshot.in", "r", stdin);
// freopen("slingshot.out", "w", stdout);
int t = 1;
// cin >> t;
while(t--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Incorrect |
5 ms |
9724 KB |
Output isn't correct |
| 3 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
| 4 |
Incorrect |
9 ms |
9856 KB |
Output isn't correct |
| 5 |
Incorrect |
8 ms |
9940 KB |
Output isn't correct |
| 6 |
Incorrect |
8 ms |
10196 KB |
Output isn't correct |
| 7 |
Incorrect |
11 ms |
10244 KB |
Output isn't correct |
| 8 |
Incorrect |
12 ms |
10452 KB |
Output isn't correct |
| 9 |
Incorrect |
18 ms |
11140 KB |
Output isn't correct |
| 10 |
Incorrect |
40 ms |
12624 KB |
Output isn't correct |
| 11 |
Incorrect |
40 ms |
13380 KB |
Output isn't correct |
| 12 |
Incorrect |
85 ms |
17096 KB |
Output isn't correct |
| 13 |
Incorrect |
98 ms |
18628 KB |
Output isn't correct |
| 14 |
Incorrect |
113 ms |
20168 KB |
Output isn't correct |
| 15 |
Incorrect |
127 ms |
20836 KB |
Output isn't correct |
| 16 |
Incorrect |
133 ms |
21524 KB |
Output isn't correct |
| 17 |
Incorrect |
156 ms |
22380 KB |
Output isn't correct |
| 18 |
Incorrect |
132 ms |
23136 KB |
Output isn't correct |
| 19 |
Incorrect |
159 ms |
23840 KB |
Output isn't correct |
| 20 |
Incorrect |
183 ms |
24552 KB |
Output isn't correct |
