oj.uz

Submission #832874

# Submission time Handle Problem Language Result Execution time Memory
832874 2023-08-21T16:09:00 Z mat_jur trapezoid (balkan11_trapezoid) C++14
46 / 100
 154 ms 17288 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << "," << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";for(auto e:x)o<< e << ", ";return o<<"}";}
#define debug(X) cerr << "["#X"]:" << X << '\n';
#else 
#define debug(X) ;
#endif
#define ll long long
#define trapez tuple<int, int, int, int, int>

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("trapezoid.in", "r", stdin);
//	freopen("trapezoid.out", "w", stdout);

	int n;
	cin >> n;
	vector<tuple<int, int, int, int, int>> v;
	map<int, int> M;
	for (int i = 0; i < n; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		v.emplace_back(make_tuple(a, b, c, d, i));
		M[c]; M[d];
	}
	M[0];
	int x = 0;
	for (auto &e : M) {
		e.second = x++;
	}
	x--;
	sort(v.begin(), v.end());
	auto cmp = [&](trapez a, trapez b) {return get<1>(a) > get<1>(b);};
	priority_queue<trapez, vector<trapez>, decltype(cmp)> Q(cmp);
	vector<pair<int, int>> dp(n);
	pair<int, int> res = {0, 0};

	int base = 1;
	while (base < x) base *= 2;
	vector<pair<int, int>> tree(2*base);
	auto merge = [&](pair<int, int> a, pair<int, int> b) {
		if (a.first == b.first) return make_pair(a.first, b.second+a.second);
		if (a.first > b.first) return a;
		else return b;
	};
	auto update = [&](int v, pair<int, int> x) {
		v += base;
		while (v > 0) {
			tree[v] = merge(tree[v], x);
			v /= 2;
		}
	};
	auto query = [&](int a, int b) {
		a += base-1;
		b += base+1;
		pair<int, int> res = {0, 0};
		while (a/2 != b/2) {
			if (a%2 == 0) res = merge(res, tree[a+1]);
			if (b%2 == 1) res = merge(res, tree[b-1]);
			a /= 2; b /= 2;
		}
		return res;
	};
	for (auto &[a, b, c, d, idx] : v) {
		while (!Q.empty() && get<1>(Q.top()) < a) {
			update(M[get<3>(Q.top())], dp[get<4>(Q.top())]);
			Q.pop();
		}
		dp[idx] = query(0, M[c]);
		dp[idx].first++;
		if (dp[idx].first == 1) dp[idx].second = 1;
		res = merge(res, dp[idx]);
		Q.push(make_tuple(a, b, c, d, idx));
	}
	
	cout << res.first << ' ' << res.second << '\n';

	return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:68:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |  for (auto &[a, b, c, d, idx] : v) {
      |             ^

Subtask #1
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 1 ms 396 KB Partially correct
5 Partially correct 2 ms 596 KB Partially correct
6 Partially correct 3 ms 844 KB Partially correct
7 Partially correct 4 ms 980 KB Partially correct
8 Partially correct 6 ms 1364 KB Partially correct
9 Partially correct 12 ms 2344 KB Partially correct
10 Partially correct 21 ms 4320 KB Partially correct
11 Partially correct 27 ms 4944 KB Partially correct
12 Partially correct 63 ms 9084 KB Partially correct
13 Partially correct 75 ms 10292 KB Partially correct
14 Partially correct 94 ms 13576 KB Partially correct
15 Partially correct 107 ms 14356 KB Partially correct
16 Partially correct 125 ms 15192 KB Partially correct
17 Partially correct 128 ms 15648 KB Partially correct
18 Partially correct 125 ms 16012 KB Partially correct
19 Partially correct 121 ms 16720 KB Partially correct
20 Partially correct 154 ms 17288 KB Partially correct