oj.uz

Submission #1037940

# Submission time Handle Problem Language Result Execution time Memory
1037940 2024-07-29T10:42:52 Z ArshiaDadras trapezoid (balkan11_trapezoid) C++14
46 / 100
 175 ms 28704 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;
}

Compilation message

trapezoid.cpp: In function 'int Main()':
trapezoid.cpp:101:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |  for(auto [seg, wh] : E){
      |           ^

Subtask #1
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18776 KB Output is correct
2 Correct 4 ms 18900 KB Output is correct
3 Partially correct 4 ms 18780 KB Partially correct
4 Partially correct 6 ms 18780 KB Partially correct
5 Partially correct 6 ms 19036 KB Partially correct
6 Partially correct 7 ms 19292 KB Partially correct
7 Partially correct 8 ms 19300 KB Partially correct
8 Partially correct 11 ms 19460 KB Partially correct
9 Partially correct 18 ms 19928 KB Partially correct
10 Partially correct 33 ms 20952 KB Partially correct
11 Partially correct 44 ms 22992 KB Partially correct
12 Partially correct 83 ms 24892 KB Partially correct
13 Partially correct 107 ms 25544 KB Partially correct
14 Partially correct 121 ms 27080 KB Partially correct
15 Partially correct 134 ms 26796 KB Partially correct
16 Partially correct 165 ms 27844 KB Partially correct
17 Partially correct 149 ms 27580 KB Partially correct
18 Partially correct 153 ms 28704 KB Partially correct
19 Partially correct 170 ms 28188 KB Partially correct
20 Partially correct 175 ms 28588 KB Partially correct