답안 #632999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
632999	2022-08-21T11:39:34 Z	gromperen	사다리꼴 (balkan11_trapezoid)	C++17	100 / 100	113 ms	11200 KB

trapezoid

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

#define ll long long
using pii = pair<int,long long>;

const int MOD = 30013;
const int INF = 1e9+7;
const int MAXN = 4e5+69;

pii fen[MAXN+5];
int id[MAXN];
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
//vector<int> id(MAXN,-1);


void upd(int i, pii v) {
	i++;
	for (; i < MAXN; i += (i & -i)) {
		if (fen[i].first < v.first) {
			fen[i].first = v.first;
			fen[i].second = v.second % MOD;
		} else if (fen[i].first == v.first) {
			fen[i].second += v.second;
			fen[i].second %= MOD;
		}

	}
}

pii query(int i) {
	i++;
	pii ans = {-1, 0};

	for (; i > 0; i -= (i & -i)) {
		if (fen[i].first > ans.first) {
			ans.first = fen[i].first;
			ans.second = fen[i].second;
		} else if (fen[i].first == ans.first) {
			ans.second += fen[i].second;
			ans.second %= MOD;
		}
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(id, -1, sizeof(id));

	int n; cin >> n;
	//vector<pair<pii, pii>> v(n+2);
	//vector<int> a(n+2), b(n+2), c(n+2), d(n+2);
	vector<int> coords;
	for (int i = 0; i <n ; ++i) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		coords.push_back(a[i]);
		coords.push_back(b[i]);
		coords.push_back(c[i]);
		coords.push_back(d[i]);
	}
	// to avoid using neutral element
	coords.push_back(0);
	coords.push_back(INF);
	a[n] = b[n] = c[n] = d[n] = 0;
	a[n+1] = b[n+1] = c[n+1] = d[n+1] = INF;


	sort(coords.begin(), coords.end()); coords.erase(unique(coords.begin(), coords.end()));
	//vector<int> id(coords.size()+5,-1);
	for (int i = 0; i <= n+1; ++i) {
		a[i] = lower_bound(coords.begin(), coords.end(), a[i]) - coords.begin();
		b[i] = lower_bound(coords.begin(), coords.end(), b[i]) - coords.begin();
		c[i] = lower_bound(coords.begin(), coords.end(), c[i]) - coords.begin();
		d[i] = lower_bound(coords.begin(), coords.end(), d[i]) - coords.begin();
		id[a[i]] = id[b[i]] = i;
	}

	upd(0, {1,1}); // add trap at 0 to avoid using neutral element
	vector<pii> dp(n+5);
	for (int i = 1; i < (int)coords.size();++i) {
		if (id[i]==-1) continue;
		int cur = id[i];
		if (i == a[cur]) {
			dp[cur] = query(c[cur]);
			dp[cur].first++;
		}
		if (i == b[cur]) {
			upd(d[cur], dp[cur]);
		}
	}
	pii ans = query(MAXN-5);
	cout << ans.first - 2 << " " << ans.second % MOD << "\n";







	return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1876 KB	Output is correct
2	Correct	1 ms	1876 KB	Output is correct
3	Correct	2 ms	2004 KB	Output is correct
4	Correct	2 ms	1964 KB	Output is correct
5	Correct	3 ms	2132 KB	Output is correct
6	Correct	5 ms	2228 KB	Output is correct
7	Correct	4 ms	2260 KB	Output is correct
8	Correct	6 ms	2388 KB	Output is correct
9	Correct	14 ms	2852 KB	Output is correct
10	Correct	26 ms	3584 KB	Output is correct
11	Correct	26 ms	4424 KB	Output is correct
12	Correct	67 ms	6548 KB	Output is correct
13	Correct	71 ms	8096 KB	Output is correct
14	Correct	103 ms	9296 KB	Output is correct
15	Correct	89 ms	8612 KB	Output is correct
16	Correct	99 ms	9660 KB	Output is correct
17	Correct	106 ms	10720 KB	Output is correct
18	Correct	97 ms	8964 KB	Output is correct
19	Correct	112 ms	10416 KB	Output is correct
20	Correct	113 ms	11200 KB	Output is correct