QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#541263 | #8783. Cherry Picking | Nanani# | WA | 1ms | 7904kb | C++20 | 2.7kb | 2024-08-31 19:01:57 | 2024-08-31 19:01:58 |
Judging History
answer
//by 72
#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
#define Fd(i, a, b) for(int i = a; i >= b; i --)
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define int long long
using namespace std;
const int mod = 998244353;
const int N = 2e5 + 10;
const int inf = 1e18;
typedef array<int, 3> a3;
typedef long long ll;
const int mx = 1e5;
int n, m, a[N];
int f[N][20], lg[N];
int rt[N], rs[N << 5], ls[N << 5], idx, g[N << 5];
void update(int &rt, int lst, int l, int r, int w) {
rt = ++ idx;
ls[rt] = ls[lst], rs[rt] = rs[lst], g[rt] = g[lst] + 1;
if(l == r) return;
int mid = l + r >> 1;
if(w <= mid) update(ls[rt], ls[lst], l, mid, w);
else update(rs[rt], rs[lst], mid + 1, r, w);
}
int call(int rrt, int lrt, int l, int r, int k) {
if(l == r) return l;
int vr = g[rs[rrt]] - g[rs[lrt]];
int mid = l + r >> 1;
if(vr >= k) return call(rs[rrt], rs[lrt], mid + 1, r, k);
else return call(ls[rrt], ls[lrt], l, mid, k - vr);
} // 区间第k大
int queryk(int l, int r, int k) {
if(l == 0) l ++;
if(r == n + 1) r --;
if(l > r) return 0;
if(r - l + 1 < k) return 0;
return call(rt[r], rt[l - 1], 1, mx, k);
}
void init() {
F(i, 2, n) lg[i] = lg[i >> 1] + 1;
F(j, 1, lg[n]) F(i, 1, n + 1 - (1 << j)) {
f[i][j] = max(f[i][j - 1], f[i + (1ll << (j - 1))][j - 1]);
}
}
int cal(int l, int r) {
if(l == 0) l = 1;
if(r == n + 1) r = n;
int len = lg[r - l + 1];
return max(f[l][len], f[r + 1 - (1ll << len)][len]);
}
void sol() {
cin >> n >> m;
F(i, 1, n) cin >> a[i];
string s; cin >> s;
s = '0' + s + '0';
F(i, 1, n) {
int w = 0;
if(s[i] == '0') f[i][0] = a[i];
else w = a[i];
update(rt[i], rt[i - 1], 1, mx, w);
}
// F(i, 1, n) F(j, i, n) cout << i << " " << j << " " << queryk(i, j, 2) << "!\n";
init();
int res = 0;
F(i, 0, n + 1) {
if(s[i] == '1') continue;
int l, r;
int ll = 0, rr = i;
while(ll < rr) {
int mid = ll + rr >> 1;
if(cal(mid, i) <= a[i]) rr = mid;
else ll = mid + 1;
}
l = ll;
ll = i, rr = n + 1;
while(ll < rr) {
int mid = ll + rr + 1 >> 1;
if(cal(i, mid) <= a[i]) ll = mid;
else rr = mid - 1;
}
r = ll;
int tmp = queryk(l, r, m);
// cout << i << " " << l << " " << r << "!!\n";
// cout << tmp << "!!!!\n";
if(tmp >= a[i]) res = max(res, tmp);
}
cout << res << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
F(i, 1, t) sol();
return 0;
}
//sldl
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7904kb
input:
5 2 1 2 3 4 5 01101
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7668kb
input:
5 2 3 4 5 2 1 10101
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 5876kb
input:
1 1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 7700kb
input:
1 1 1 0
output:
1
result:
wrong answer expected '0', found '1'