Submission #200252

#	Time	Username	Problem	Language	Result	Execution time	Memory
200252		Diuven	trapezoid (balkan11_trapezoid)	C++14	100 / 100	186 ms	31468 KiB

trapezoid

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

typedef pair<int, int> pii;

const int MOD = 30013;
const int MAX = 1e5+10;
const int LG  = 18;

inline int _max(int x, int y){ return x>y ? x : y; }
inline pii add(const pii& x, const pii& y){
	pii res = {_max(x.first, y.first), 0};
	if(res.first==x.first) res.second += x.second;
	if(res.first==y.first) res.second += y.second;
	res.second %= MOD;
	return res;
}

int n;
vector<int> X, Y;
// find maximum below x (inclusive)
int find(int x, vector<int>& V){ return upper_bound(V.begin(), V.end(), x) - V.begin() - 1; }
struct tra {
	int a, b, c, d;
	void in(){
		cin>>a>>b>>c>>d;
		X.push_back(b); Y.push_back(d);
	}
} R[MAX];

struct node {
	int l, r; pii p;
} T[MAX * LG];
int rt[MAX], bck;

int make(int v, int s, int e, int y, pii pp){
	if(y<s || e<y) return v;
	T[++bck] = T[v]; v = bck;
	if(s==e){ T[v].p = pp; return v; }
	T[v].l = make(T[v].l, s, (s+e)/2, y, pp);
	T[v].r = make(T[v].r, (s+e)/2+1, e, y, pp);
	T[v].p = add(T[T[v].l].p, T[T[v].r].p);
	return v;
}
pii get(int v, int s, int e, int qr){
	if(qr<s) return {0,0};
	if(e<=qr) return T[v].p;
	return add(get(T[v].l, s, (s+e)/2, qr), get(T[v].r, (s+e)/2+1, e, qr));
}

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

	cin>>n;
	for(int i=1; i<=n; i++) R[i].in();
	X.push_back(0); Y.push_back(0);
	sort(X.begin(), X.end());
	sort(Y.begin(), Y.end());
	for(int i=1; i<=n; i++){
		R[i].a = find(R[i].a, X);
		R[i].b = find(R[i].b, X);
		R[i].c = find(R[i].c, Y);
		R[i].d = find(R[i].d, Y);
	}
	sort(R+1, R+n+1, [](tra& x, tra& y){ return x.b < y.b; });

	pii ans = {0,1};
	rt[0] = make(0, 0, n, 0, {0,1});

	for(int i=1; i<=n; i++){
		int x = R[i].a, y = R[i].c;
		pii now = get(rt[x], 0, n, y);
		// if(now.first==0 && now.second==0) now.second++;
		now.first++;
		ans = add(ans, now);
		rt[i] = make(rt[i-1], 0, n, R[i].d, now);
	}
	cout<<ans.first<<' '<<ans.second<<'\n';

	return 0;
}

• Subtask 1: 100 / 100