Submission #788745

#	Time	Username	Problem	Language	Result	Execution time	Memory
788745		acatmeowmeow	Exhibition (JOI19_ho_t2)	C++11	0 / 100	1 ms	340 KiB

joi2019_ho_t2

#include <bits/stdc++.h>

using namespace std;

#define int long long 

const int N = 1e5;
int n, m, S[N + 5], V[N + 5], C[N + 5], arr[N + 5], dp[N + 5];
pair<int, int> tree[N + 5];

pair<int, int> combine(pair<int, int>a, pair<int, int>b) {
	if (a.first > b.first) return a;
	else if (a.first < b.first) return b;
	else return {a.first, min(a.second, b.second)};
}

void update(int n, int k, pair<int, int>v) {
	for (; k <= n; k += k&-k) tree[k] = combine(tree[k], v);
}

pair<int, int> query(int k) {
	pair<int, int> ans = {0, 0};
	for (; k; k -= k&-k) ans = combine(ans, tree[k]);
	return ans;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> S[i] >> V[i];
	for (int i = 1; i <= m; i++) cin >> C[i];

	for (int i = 1; i <= n; i++) arr[i] = i;	
	sort(arr + 1, arr + n + 1, [&](int a, int b) { 
			if (V[a] == V[b]) return S[a] < S[b];
			else return V[a] < V[b];
	});

	sort(C + 1, C + m + 1);
	C[m + 1] = 1e18;
	
	vector<int> par(n + 5);
	for (int i = 1; i <= n; i++) {
		if (S[arr[i]] > C[m]) continue;
		int l = lower_bound(C + 1, C + m + 2, S[arr[i]]) - (C + 1) + 1; 
		pair<int, int> ans = query(m - 1);
		dp[i] = ans.first + 1;
		par[i] = ans.second + 1;
		int nexPos = max(l, ans.second + 1);
		update(m, nexPos, {dp[i], nexPos});
	}
	cout << *max_element(dp + 1, dp + n + 1) << '\n';
	//for (int i = 1; i <= n; i++) cout << S[arr[i]] << " " << C[par[i]] << " " << dp[i] << '\n';
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50