Submission #1037941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037941		ArshiaDadras	trapezoid (balkan11_trapezoid)	C++17	46 / 100	181 ms	26672 KiB

trapezoid

#include <bits/stdc++.h>

#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second


using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef long double ld;

typedef array<ld, 3> P;


const int N = 4e5 + 10;
const int Mod = 1000000007;


int a[N], b[N], c[N], d[N];


pii seg[N << 2];

pii Merge(const pii& A, const pii& B){
	return {max(A.F, B.F), ((A.F >= B.F ? A.S : 0) + (A.F <= B.F ? B.S : 0)) % Mod};
}

void Change(int id, int x, pii nw, int L, int R){
	if(L + 1 == R){
		seg[id] = Merge(seg[id], nw);
		return ;
	}
	int mid = (L + R) >> 1;
	if(x < mid) Change(id << 1, x, nw, L, mid);
	else Change(id << 1 | 1, x, nw, mid, R);
	seg[id] = Merge(seg[id << 1], seg[id << 1 | 1]);
}

pii Get(int id, int l, int r, int L, int R){
	if(r <= L || R <= l) return pii(0, 0);
	if(l <= L && R <= r) return seg[id];
	int mid = (L + R) >> 1;
	return Merge(Get(id << 1, l, r, L, mid), Get(id << 1 | 1, l, r, mid, R));
}


pii dp[N];

int Main(){

	int n;
	cin >> n;
	rep(i, 0, n){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		if(a[i] > b[i]) swap(a[i], b[i]);
		if(c[i] > d[i]) swap(c[i], d[i]);
	}
	vi U, D;
	rep(i, 0, n) U.pb(a[i]);
	rep(i, 0, n) U.pb(b[i]);

	rep(i, 0, n) D.pb(c[i]);
	rep(i, 0, n) D.pb(d[i]);

	sort(all(U));
	sort(all(D));

	int a0 = 0;

	vector<pair<pii, pii> > E;
	rep(i, 0, n){
		if(a[i] == b[i] && c[i] == d[i]){
			a0 ++;
			continue;
		}

		a[i] = lower_bound(all(U), a[i]) - U.begin();
		b[i] = lower_bound(all(U), b[i]) - U.begin();

		c[i] = lower_bound(all(D), c[i]) - D.begin();
		d[i] = lower_bound(all(D), d[i]) - D.begin();
		
		E.pb({{a[i], c[i]}, {1, i}});
		E.pb({{b[i], d[i]}, {0, i}});
	}
	assert(a0 == 0);

	pii res = {0, 1};

	sort(all(E));

	Change(1, 0, pii(0, 1), 0, N);

	for(auto [seg, wh] : E){
		// cerr << "!! " << seg.F << ' ' << seg.S << " : " << wh.F << ' ' << wh.S << '\n';
		if(wh.F == 0){ // update
			Change(1, seg.S, dp[wh.S], 0, N);
		} else {
			dp[wh.S] = Get(1, 0, seg.S + 1, 0, N);
			dp[wh.S].F ++;
		}
	}

	// res = {0, 1};
	// rep(i, 1, n) if(dp[i].F >= 1)
	// 	res = Merge(res, dp[i]);
	res = Get(1, 0, N, 0, N);
	cout << res.F + a0 << ' ' << res.S << '\n';
	return 0;
}

int main(){

	fill(seg, seg + (N << 2), pii(0, 0));
	// rep(i, 2, N) for(int j = i + i; j < N; j+=i) pr[j] = 1;
	// fb[0] = fb[1] = 1;
	// rep(i, 2, N){
	// 	if(pr[i]) fb[i] = (fb[i - 1] + fb[i - 2]) % 1000000;
	// 	else fb[i] = fb[i - 1] + fb[i - 2] + i;
	// }
	int tc = 1;
	// cin >> tc;
	while(tc--) Main();



	return 0;
}

• Subtask 1: 46 / 100