QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#541263#8783. Cherry PickingNanani#WA 1ms7904kbC++202.7kb2024-08-31 19:01:572024-08-31 19:01:58

Judging History

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

  • [2024-08-31 19:01:58]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7904kb
  • [2024-08-31 19:01:57]
  • 提交

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'