Submission #541160

#	Time	Username	Problem	Language	Result	Execution time	Memory
541160		akhan42	trapezoid (balkan11_trapezoid)	C++17	100 / 100	153 ms	22904 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;
ii otr2dep[MX];
int mod = 30013;


int vu2c(int v) {
	return lower_bound(all(vu), v) - vu.begin();
}

int vb2c(int v) {
	return lower_bound(all(vb), v) - vb.begin();
}

int add(int a, int b) {
	return (a + b) % mod;
}

void addm(int& a, int b) {
	a = (a + b) % mod;
}


struct Seg {
	int n;
	vii mx;

	Seg(int n): n(n) {
		mx.assign(2 * n, {-1, 0});
	}

	static void combm(ii& res, ii val) {
		if(res.F < val.F) {
			res = val;
		}
		else if(res.F == val.F) {
			addm(res.S, val.S);
		}
	}

	ii comb(ii a, ii b) {
		if(a.F < b.F) {
			return b;
		}
		else if(a.F == b.F) {
			return {a.F, add(a.S, b.S)};
		}
		else {
			return a;
		}
	}

	ii query(int l, int r) {
		ii res = {-1, 0};
		for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
			if(l & 1) combm(res, mx[l++]);
			if(r & 1) combm(res, mx[--r]);
		}
		return res;
	}

	void update(int p, ii v) {
		for(combm(mx[p += n], v); p > 1; p >>= 1) {
			mx[p >> 1] = comb(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]) {
			ii dep_ct = seg.query(0, ul[i] - 1);
			dep_ct.F += 1;
			if(dep_ct.F == 0)
				dep_ct.S = 1;
			otr2dep[i] = dep_ct;

//			cout << i + 1 << ' ' << dep_ct.F << ' ' << dep_ct.S << '\n';
		}
		for(int i: r2i[botc]) {
			seg.update(ur[i], otr2dep[i]);
		}
	}

	ii mx = {-1, 0};
	forn(i, n)
		Seg::combm(mx, otr2dep[i]);

	cout << mx.F + 1 << ' ' << mx.S << '\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: 100 / 100