oj.uz

Submission #541157

# Submission time Handle Problem Language Result Execution time Memory
541157 2022-03-22T12:02:49 Z akhan42 trapezoid (balkan11_trapezoid) C++17
40 / 100
 151 ms 21256 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;
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;
		}
		for(int i: r2i[botc]) {
			seg.update(ur[i], otr2dep[i]);
		}
	}

	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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 9684 KB Partially correct
2 Partially correct 6 ms 9720 KB Partially correct
3 Partially correct 6 ms 9728 KB Partially correct
4 Partially correct 7 ms 9860 KB Partially correct
5 Partially correct 8 ms 9940 KB Partially correct
6 Partially correct 8 ms 10152 KB Partially correct
7 Partially correct 10 ms 10244 KB Partially correct
8 Partially correct 10 ms 10324 KB Partially correct
9 Partially correct 17 ms 11016 KB Partially correct
10 Partially correct 27 ms 12168 KB Partially correct
11 Partially correct 35 ms 12732 KB Partially correct
12 Partially correct 71 ms 15608 KB Partially correct
13 Partially correct 82 ms 16696 KB Partially correct
14 Partially correct 97 ms 17896 KB Partially correct
15 Partially correct 110 ms 18408 KB Partially correct
16 Partially correct 141 ms 19040 KB Partially correct
17 Partially correct 151 ms 19620 KB Partially correct
18 Partially correct 118 ms 20136 KB Partially correct
19 Partially correct 123 ms 20748 KB Partially correct
20 Partially correct 138 ms 21256 KB Partially correct