QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#699166#8783. Cherry PickingMaybe_TomorrowWA 0ms3648kbC++201.9kb2024-11-02 02:41:152024-11-02 02:41:16

Judging History

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

  • [2024-11-02 02:41:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3648kb
  • [2024-11-02 02:41:15]
  • 提交

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 (i == n - 1 || w[i + 1] != 1) { // End of ones interval
				oneidx++;
			}
		}
	}

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

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

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

	cout << "0\n";
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3644kb

input:

5 2
1 2 3 4 5
01101

output:

2

result:

ok answer is '2'

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3648kb

input:

5 2
3 4 5 2 1
10101

output:

5

result:

wrong answer expected '0', found '5'