QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#622960#8783. Cherry PickingSword1E1WA 2ms11916kbC++201.8kb2024-10-09 08:59:022024-10-09 08:59:03

Judging History

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

  • [2024-10-09 08:59:03]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11916kb
  • [2024-10-09 08:59:02]
  • 提交

answer

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

#define dbg(x...) \
do { \
std::cout << #x << " -> "; \
err(x); \
} while (0)

void err() {
	std::cout << std::endl;
}

template<class T, class... Ts>
void err(T arg, Ts &... args) {
	std::cout << fixed << setprecision(10) << arg << ' ';
	err(args...);
}

const int maxn = 1e5 + 5;
int a[maxn];
string res;
vector<int>p[maxn];
struct SegTree {
#define ls(p) p << 1
#define rs(p) p << 1 | 1
	int L[maxn << 2],R[maxn << 2],V[maxn << 2],Siz[maxn << 2];
	
	inline void Push_up(int i) {
		if (L[ls(i)] == Siz[ls(i)]) L[i] = L[ls(i)] + L[rs(i)];
		else L[i] = L[ls(i)];
		if (R[rs(i)] == Siz[rs(i)]) R[i] = R[rs(i)] + R[ls(i)];
		else R[i] = R[rs(i)];
		Siz[i] = Siz[ls(i)] + Siz[rs(i)];
		V[i] = max({L[i],R[i],R[ls(i)] + L[rs(i)]});
	}
	
	void Build (int p,int l,int r) {
		if (l == r) {
			//dbg(l,Id[l]);
			Siz[p] = 1;
			V[p] = L[p] = R[p] = res[l - 1] - '0'; 
			return;
		}
		int mid = (l + r) >> 1;
		Build(ls(p),l,mid);
		Build(rs(p),mid + 1,r);
		Push_up(p);
	}
	
	void Update(int p,int l,int r,int x) {
		if (l == r) {
			L[p] = R[p] = Siz[p] = V[p] = 0;
			return;
		}
		int mid = (l + r) >> 1;
		if (x <= mid) Update(ls(p),l,mid,x);
		else Update(rs(p),mid + 1,r,x);
		Push_up(p);
	}
} Tr;


void GENSHEN_START() {
	int n,k;cin >> n >> k;
	for (int i = 1;i <= n;i++) {
		cin >> a[i];
		p[a[i]].push_back(i);
	}
	cin >> res;
	Tr.Build(1,1,n);
	int ans = 0;
	if (Tr.V[1] >= k) ans = 1;
	for (int i = 1;i <= 1e5;i++) {
		for (auto j : p[i]) {
			Tr.Update(1,1,n,j);
		}
		if (Tr.V[1] >= k) ans = i + 1;
	}
	cout << ans << '\n';
	return ;
}

signed main()
{
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int T = 1;
	//cin >> T;
	while (T--) GENSHEN_START();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 2
1 2 3 4 5
01101

output:

2

result:

ok answer is '2'

Test #2:

score: 0
Accepted
time: 2ms
memory: 11864kb

input:

5 2
3 4 5 2 1
10101

output:

0

result:

ok answer is '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 9796kb

input:

1 1
1
1

output:

1

result:

ok answer is '1'

Test #4:

score: 0
Accepted
time: 2ms
memory: 9808kb

input:

1 1
1
0

output:

0

result:

ok answer is '0'

Test #5:

score: 0
Accepted
time: 2ms
memory: 9868kb

input:

5 3
8 3 5 2 7
10101

output:

5

result:

ok answer is '5'

Test #6:

score: 0
Accepted
time: 2ms
memory: 11784kb

input:

10 3
1 10 2 3 9 3 1 6 9 3
1100110001

output:

0

result:

ok answer is '0'

Test #7:

score: 0
Accepted
time: 2ms
memory: 9872kb

input:

10 1
6 7 2 10 8 4 4 9 7 9
0111011000

output:

10

result:

ok answer is '10'

Test #8:

score: 0
Accepted
time: 0ms
memory: 9804kb

input:

10 2
4 5 9 6 9 10 6 9 2 7
1100010100

output:

9

result:

ok answer is '9'

Test #9:

score: 0
Accepted
time: 0ms
memory: 11788kb

input:

10 3
2 10 8 5 8 3 7 9 9 1
1100011100

output:

3

result:

ok answer is '3'

Test #10:

score: 0
Accepted
time: 0ms
memory: 11844kb

input:

10 5
5 5 9 2 7 2 4 8 4 8
1010001100

output:

0

result:

ok answer is '0'

Test #11:

score: 0
Accepted
time: 0ms
memory: 11792kb

input:

10 10
6 5 8 3 2 8 6 4 5 5
0111001100

output:

0

result:

ok answer is '0'

Test #12:

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

input:

100 1
13 90 87 79 34 66 76 58 65 37 63 38 84 88 89 98 63 55 16 39 64 50 28 64 4 69 40 51 75 37 11 9 20 29 36 29 30 61 38 54 92 78 72 36 78 24 78 8 98 11 2 41 64 51 45 67 27 80 67 84 73 50 99 82 39 70 84 18 54 43 85 96 59 98 82 5 57 46 68 31 97 89 21 65 57 37 58 25 30 40 15 76 44 85 75 65 22 97 93 82...

output:

90

result:

wrong answer expected '97', found '90'