Submission #584070

#	Time	Username	Problem	Language	Result	Execution time	Memory
584070		penguinhacker	trapezoid (balkan11_trapezoid)	C++17	100 / 100	74 ms	9976 KiB

trapezoid

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

#define ll long long
#define ar array

const int mxN=1e5, M=30013;
int n;
ar<int, 4> trap[mxN];
ar<int, 2> ord[2*mxN], e[2*mxN], dp[mxN], ft[2*mxN+1];
bool vis[mxN];

ar<int, 2> cmb(ar<int, 2> a, ar<int, 2> b) {
	return a[0]!=b[0]?a[0]>b[0]?a:b:ar<int, 2>{a[0], (a[1]+b[1])%M};
}

void upd(int i, ar<int, 2> x) {
	for (++i; i<=2*n; i+=i&-i)
		ft[i]=cmb(ft[i], x);
}

ar<int, 2> qry(int i) {
	ar<int, 2> r={};
	for (++i; i; i-=i&-i)
		r=cmb(r, ft[i]);
	return r;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; ++i) {
		cin >> trap[i][0] >> trap[i][1] >> trap[i][2] >> trap[i][3];
		e[2*i]={trap[i][0], i};
		e[2*i+1]={trap[i][1], i};
		ord[2*i]={trap[i][2], 2*i};
		ord[2*i+1]={trap[i][3], 2*i+1};
	}
	sort(e, e+2*n);
	sort(ord, ord+2*n);
	for (int i=0; i<2*n; ++i)
		trap[ord[i][1]/2][2+ord[i][1]%2]=i;
	for (int event=0; event<2*n; ++event) {
		int i=e[event][1];
		//cout << i << " " << trap[i][2] << " " << trap[i][3] << endl;
		if (!vis[i]) {
			dp[i]=qry(trap[i][2]);
			++dp[i][0];
			if (dp[i][0]==1) {
				assert(dp[i][1]==0);
				dp[i][1]=1;
			}
			vis[i]=1;
		} else {
			upd(trap[i][3], dp[i]);
		}
	}
	ar<int, 2> ans=qry(2*n);
	cout << ans[0] << " " << ans[1];
	return 0;
}

• Subtask 1: 100 / 100