oj.uz

Submission #541160

# Submission time Handle Problem Language Result Execution time Memory
541160 2022-03-22T12:22:30 Z akhan42 trapezoid (balkan11_trapezoid) C++17
100 / 100
 153 ms 22904 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9636 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9872 KB Output is correct
5 Correct 9 ms 9952 KB Output is correct
6 Correct 8 ms 10144 KB Output is correct
7 Correct 9 ms 10280 KB Output is correct
8 Correct 13 ms 10324 KB Output is correct
9 Correct 18 ms 11108 KB Output is correct
10 Correct 30 ms 12360 KB Output is correct
11 Correct 40 ms 13016 KB Output is correct
12 Correct 75 ms 16352 KB Output is correct
13 Correct 88 ms 17608 KB Output is correct
14 Correct 105 ms 18932 KB Output is correct
15 Correct 120 ms 19624 KB Output is correct
16 Correct 126 ms 20272 KB Output is correct
17 Correct 128 ms 21028 KB Output is correct
18 Correct 124 ms 21600 KB Output is correct
19 Correct 134 ms 22328 KB Output is correct
20 Correct 153 ms 22904 KB Output is correct