题解 - P10134 Cowmpetency

Luogu

分析

在更新奶牛的牲任力分数序列中：

  • 如果某个奶牛的牲任力分数已知，则将其标记为已访问；
  • 如果某个奶牛的分数未知，记录其下标，并将其添加到一个集合中。

然后可以根据记忆信息更新分数：
对于每个数对 $(a_j,h_j)$，找到区间内未知分数的奶牛，根据规则更新其分数,同时判断，确保序列满足条件。

赛时 AC 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
using namespace std;

long long n, q, c, tp;
long long mp[1000001], mp2[1000001], mp3[1000001], isv[1000001];
pair<long long, long long> pairl[1000001];
set<long long> setl;

bool cmp(pair<long long, long long> a, pair<long long, long long> b) {
	return (a.second == b.second) ? (a.first < b.first) : (a.second < b.second);
}

void solve() {
	setl.clear();
	cin >> n >> q >> c;
	for (long long i = 1; i <= n; i++) {
		cin >> mp[i];
		if (!mp[i]) {
			setl.insert(i);
			isv[i] = 1;
		} else {
			isv[i] = 0;
		}
		mp3[i] = max(mp3[i - 1], mp[i]);
	}
	for (long long i = 1; i <= q; i++) {
		cin >> pairl[i].first >> pairl[i].second;
	}

	sort(pairl + 1, pairl + q + 1, cmp);
	tp = 0;

	for (long long i = 1; i <= q; i++) {
		if (pairl[i].first < tp && pairl[i].second != tp) {
			cout << "-1";
			return;
		}
		tp = pairl[i].second;
	}

	tp = n + 1;
	for (long long i = q; i >= 1; i--) {
		long long a = min(pairl[i].second - 1, tp), b = pairl[i].first + 1;

		for (long long j = a; j >= b; j--) {
			if (!isv[j] && mp[j] > mp3[pairl[i].first]) {
				set<long long>::iterator tp2 = setl.upper_bound(pairl[i].first);
				if (tp2 == setl.begin()) {
					cout << "-1";
					return;
				}
				--tp2;
				long long tp3 = *tp2;
				mp[tp3] = max(mp[tp3], mp[j]);
			} else if (isv[j] && mp[j] > mp3[pairl[i].first]) {
				set<long long>::iterator tp2 = setl.upper_bound(pairl[i].first);
				if (tp2 == setl.begin()) {
					cout << "-1";
					return;
				}
				--tp2;
				long long tp3 = *tp2;
				mp[tp3] = max(mp[tp3], mp[j]);
				mp[j] = 0;
			}
		}
		tp = pairl[i].first;
	}
	tp = 0;
	for (long long i = 1; i <= q; i++) {
		long long x = pairl[i].second, j;
		stack<long long> r;
		for (j = i; j <= q && pairl[j].second == x; j++) {
			r.push(pairl[j].first);
		}
		long long maxn = 0;
		if (r.size() && tp == r.top()) {
			maxn = max(maxn, mp2[tp]);
			r.pop();
		}
		for (long long k = tp + 1; k <= x - 1; k++) {
			if (!mp[k])
				mp[k] = 1;
			if (maxn && mp[k] > maxn) {
				cout << "-1";
				return;
			}
			mp2[k] = max(mp2[k - 1], mp[k]);
			if (r.size() && k == r.top()) {
				maxn = max(maxn, mp2[k]);
				r.pop();
			}
		}
		if (isv[x])
			mp[x] = max(mp[x], maxn + 1);
		else if (maxn >= mp[x]) {
			cout << "-1";
			return;
		}
		mp2[x] = max(mp2[x - 1], mp[x]);
		tp = x;
		i = j - 1;
	}
	for (long long i = tp + 1; i <= n; i++) {
		if (!mp[i])
			mp[i] = 1;
		mp2[i] = max(mp2[i - 1], mp[i]);
	}
	if (mp2[n] > c) {
		cout << "-1";
		return;
	}
	for (long long i = 1; i <= n; i++) {
		cout << mp[i];
		if (i != n) {
			cout << " ";
		}
	}
	return;
}

int main() {
	long long T;
	cin >> T;

	while (T--) {
		solve();
		cout<<endl;
	}

	return 0;
}