Submission #1283735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283735		peteza	trapezoid (balkan11_trapezoid)	C++20	100 / 100	108 ms	16872 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
const int mod = 30013;

int n, a, b, c, d;
vector<pair<int, int>> qr[200005];
vector<int> uppers, lowers;

pair<int, int> fwk[200005], up[200005], low[200005];
bool vis[200005];
pair<int, int> ans[200005];

int idx(vector<int> &vec, int val) {
	auto it = upper_bound(vec.begin(), vec.end(), val);
	return it - vec.begin();
}

void upd(int x, pair<int, int> val) {
	for(;x<200004;x+=x&-x) {
		if(fwk[x].first == val.first) fwk[x].second += val.second;
		else if(fwk[x].first < val.first) fwk[x] = val;
		if(fwk[x].second >= mod) fwk[x].second -= mod;
	}
}

pair<int, int> qry(int x) {
	pair<int, int> sm(-1, 0);
	for(;x;x-=x&-x) {
		if(sm.first == fwk[x].first) sm.second += fwk[x].second;
		else if(sm.first < fwk[x].first) sm = fwk[x];
		if(sm.second >= mod) sm.second -= mod;
	}
	return sm;
}

int main() {
	cin.tie(0) -> sync_with_stdio(0);
	cin >> n;
	for(int i=1;i<=n;i++) {
		cin >> a >> b >> c >> d;
		uppers.push_back(a);
		uppers.push_back(b);
		lowers.push_back(c);
		lowers.push_back(d);
		up[i] = {a, b};
		low[i] = {c, d};
		//qr[a].emplace_back(i, -1);
		//qr[b].emplace_back(i, -1);
	}
	sort(uppers.begin(), uppers.end());
	lowers.push_back(-999999999);
	sort(lowers.begin(), lowers.end());
	//lowers.push_back(-99999999);
	uppers.resize(unique(uppers.begin(), uppers.end()) - uppers.begin());
	lowers.resize(unique(lowers.begin(), lowers.end()) - lowers.begin());
	for(int i=1;i<=n;i++) {
		qr[idx(uppers, up[i].first) ].emplace_back(i, -1);
		qr[idx(uppers, up[i].second)].emplace_back(i, -1);
	}
	fill(fwk, fwk+200004, pair<int, int>(-1, 0));
	upd(1, pair<int, int>(0, 1));
	pair<int, long long> ansans(-1, 0);
	for(int i=0;i<=2*n;i++) {
		sort(qr[i].begin(), qr[i].end());
		for(auto &e:qr[i]) {
			if(vis[e.first]) {
				upd(idx(lowers, low[e.first].second), ans[e.first]);
			} else {
				vis[e.first] = 1;
				ans[e.first] = qry(idx(lowers, low[e.first].first-1));
				ans[e.first].first++;
				if(ans[e.first].first == ansans.first) {
					ansans.second += ans[e.first].second;
				} else if(ans[e.first].first > ansans.first) {
					ansans = ans[e.first];
				}
				//cout << low[e.first].first << "\n";
				//cout << idx(lowers, low[e.first].first-1) << "\n";
				//cout << ans[e.first].first << " " << ans[e.first].second << "\n";	
			}
		}
	}
	cout << ansans.first << " " << ansans.second%mod;
}

• Subtask 1: 100 / 100