Submission #632996

#	Time	Username	Problem	Language	Result	Execution time	Memory
632996		gromperen	trapezoid (balkan11_trapezoid)	C++14	60 / 100	119 ms	27728 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;

#define ll long long
using pii = pair<int,long long>;

const int MOD = 30013;
const int INF = 1e9+7;
const int MAXN = 2e5+69;

pii fen[MAXN+5];

void upd(int i, pii v) {
	i++;
	for (; i < MAXN; i += (i & -i)) {
		if (fen[i].first < v.first) {
			fen[i].first = v.first;
			fen[i].second = v.second % MOD;
		} else if (fen[i].first == v.first) {
			fen[i].second += v.second;
			fen[i].second %= MOD;
		}

	}
}

pii query(int i) {
	i++;
	pii ans = {-1, 0};

	for (; i > 0; i -= (i & -i)) {
		if (fen[i].first > ans.first) {
			ans.first = fen[i].first;
			ans.second = fen[i].second;
		} else if (fen[i].first == ans.first) {
			ans.second += fen[i].second;
			ans.second %= MOD;
		}
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; cin >> n;
	vector<pair<pii, pii>> v(n+2);
	vector<int> a(n+2), b(n+2), c(n+2), d(n+2);
	vector<int> coords;
	for (int i = 0; i <n ; ++i) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		coords.push_back(a[i]);
		coords.push_back(b[i]);
		coords.push_back(c[i]);
		coords.push_back(d[i]);
	}
	// to avoid using neutral element
	coords.push_back(0);
	coords.push_back(INF);
	a[n] = b[n] = c[n] = d[n] = 0;
	a[n+1] = b[n+1] = c[n+1] = d[n+1] = INF;


	sort(coords.begin(), coords.end()); coords.erase(unique(coords.begin(), coords.end()));
	vector<int> id(coords.size()+5,-1);
	for (int i = 0; i <= n+1; ++i) {
		a[i] = lower_bound(coords.begin(), coords.end(), a[i]) - coords.begin();
		b[i] = lower_bound(coords.begin(), coords.end(), b[i]) - coords.begin();
		c[i] = lower_bound(coords.begin(), coords.end(), c[i]) - coords.begin();
		d[i] = lower_bound(coords.begin(), coords.end(), d[i]) - coords.begin();
		id[a[i]] = id[b[i]] = i;
	}

	upd(0, {1,1}); // add trap at 0 to avoid using neutral element
	vector<pii> dp(n+5);
	for (int i = 1; i < coords.size();++i) {
		if (id[i]==-1) continue;
		int cur = id[i];
		if (i == a[cur]) {
			dp[cur] = query(c[cur]);
			dp[cur].first++;
		}
		if (i == b[cur]) {
			upd(d[cur], dp[cur]);
		}
	}
	pii ans = query(MAXN-5);
	cout << ans.first - 2 << " " << ans.second % MOD << "\n";







	return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for (int i = 1; i < coords.size();++i) {
      |                  ~~^~~~~~~~~~~~~~~

• Subtask 1: 60 / 100