oj.uz

Submission #1037941

# Submission time Handle Problem Language Result Execution time Memory
1037941 2024-07-29T10:43:24 Z ArshiaDadras trapezoid (balkan11_trapezoid) C++17
46 / 100
 181 ms 26672 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Partially correct 3 ms 18944 KB Partially correct
4 Partially correct 4 ms 18780 KB Partially correct
5 Partially correct 6 ms 19072 KB Partially correct
6 Partially correct 7 ms 19168 KB Partially correct
7 Partially correct 8 ms 19164 KB Partially correct
8 Partially correct 10 ms 19340 KB Partially correct
9 Partially correct 19 ms 19672 KB Partially correct
10 Partially correct 37 ms 20180 KB Partially correct
11 Partially correct 42 ms 22340 KB Partially correct
12 Partially correct 88 ms 23624 KB Partially correct
13 Partially correct 100 ms 24012 KB Partially correct
14 Partially correct 127 ms 24648 KB Partially correct
15 Partially correct 127 ms 26256 KB Partially correct
16 Partially correct 151 ms 24780 KB Partially correct
17 Partially correct 148 ms 25288 KB Partially correct
18 Partially correct 143 ms 26672 KB Partially correct
19 Partially correct 173 ms 26048 KB Partially correct
20 Partially correct 181 ms 25928 KB Partially correct