Submission #541150

#	Time	Username	Problem	Language	Result	Execution time	Memory
541150		akhan42	trapezoid (balkan11_trapezoid)	C++17	0 / 100	183 ms	24552 KiB

trapezoid

#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();
	}
}

• Subtask 1: 0 / 100