QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#699171#8783. Cherry PickingMaybe_TomorrowWA 0ms3644kbC++202.0kb2024-11-02 02:49:272024-11-02 02:49:27

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 02:49:27]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3644kb
  • [2024-11-02 02:49:27]
  • 提交

answer

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, k;
	cin >> n >> k;

	vector<int> r(n), w(n);
	for (int &i : r) cin >> i;
    string s; cin >> s;
	for (int i = 0; i < n; i++) w[i] = s[i] - '0';

	vector<vector<int>> ones(1);  // Start with one empty vector for the first "ones" interval
	vector<pair<int, int>> maxzeros; // {max value in zero interval, corresponding ones index}
	int curmaxzero = 0, oneidx = 0;

	for (int i = 0; i < n; i++) {
		if (w[i] == 0) {
			curmaxzero = max(curmaxzero, r[i]);
			if (i == n - 1 || w[i + 1] != 0) { // End of zero interval
				maxzeros.push_back({curmaxzero, oneidx});
				curmaxzero = 0;
			}
		} else {
			if (ones.size() <= oneidx) {
				ones.push_back(vector<int>()); // Add a new vector for each "ones" interval
			}
			ones[oneidx].insert(lower_bound(ones[oneidx].begin(), ones[oneidx].end(), r[i]), r[i]);
			if (ones[oneidx].size() >= k) {
				cout << "1\n";
				return 0;
			} 
			if (i == n - 1 || w[i + 1] != 1) { // End of ones interval
				oneidx++;
			}
		}
	}

	int curmaxone = 0;
	vector<int> mergedsize(oneidx);

	sort(maxzeros.begin(), maxzeros.end());
	for (const auto& interval : maxzeros) {
		int leftone = interval.second - 1, rightone = interval.second;
		int rightmerge = 0, leftmerge = 0;

		// Check bounds before accessing `ones`
		if (rightone < oneidx) {
			rightmerge = ones[rightone].end() - upper_bound(ones[rightone].begin(), ones[rightone].end(), interval.first);
			rightmerge -= mergedsize[rightone];
			mergedsize[rightone] = rightmerge;
		}
		if (leftone >= 0) {
			leftmerge = ones[leftone].end() - upper_bound(ones[leftone].begin(), ones[leftone].end(), interval.first);
			leftmerge -= mergedsize[leftone];
			mergedsize[leftone] = leftmerge;
		}
		curmaxone += leftmerge + rightmerge;
		if (curmaxone >= k) {
			cout << interval.first + 1<< "\n";
			return 0;
		}
	}

	cout << "0\n";
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3644kb

input:

5 2
1 2 3 4 5
01101

output:

1

result:

wrong answer expected '2', found '1'