QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#545703#8783. Cherry PickinglonelywolfWA 0ms3800kbC++203.9kb2024-09-03 16:25:182024-09-03 16:25:21

Judging History

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

  • [2024-09-03 16:25:21]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3800kb
  • [2024-09-03 16:25:18]
  • 提交

answer

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

#define int long long  
template<class Info>
struct SegmentTree {
    int n;
    vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(vector(n_ + 1, v_));
    }
    template<class T>
    void init(vector<T> init_) {
        n = init_.size() - 1;
        info.assign(4 << __lg(n) + 1, Info());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = {init_[l]};
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x <= m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 1, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m + 1, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 1, n, l, r);
    }
    // 线段树二分
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F pred) {
        if (l > y || r < x || !pred(info[p])) {
            return -1;
        }
        if (l == r) {
            return l;
        }
        int m = (l + r) / 2;
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m + 1, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F pred) {
        return findFirst(1, 1, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F pred) {
        if (l > y || r < x || !pred(info[p])) {
            return -1;
        }
        if (l == r) {
            return l;
        }
        int m = (l + r) / 2;
        int res = findLast(2 * p + 1, m + 1, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F pred) {
        return findLast(1, 1, n, l, r, pred);
    }
};
struct Info {
	int sum = 0;
	int mx = 0;
	int lmx = 0;
	int rmx = 0;
};

Info operator+(Info a, Info b) {
	Info ret;

	ret.sum = a.sum + b.sum;
	ret.mx = max({a.mx, b.mx, a.rmx + b.lmx});

	ret.lmx = a.lmx;
	if (a.lmx == a.sum) {
		ret.lmx = a.lmx + b.lmx;
	}

	ret.rmx = b.rmx;
	if (b.rmx == b.sum) {
		ret.rmx = a.rmx + b.rmx;
	}
	
	return ret;
}

constexpr int inf = 1e9;

signed main() {  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  

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

	vector<int> a(n + 1);
	string r;
	map<int, vector<int>> mp;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		mp[-a[i]].push_back(i);
	}
	cin >> r;
	r = " " + r;

	SegmentTree<Info> tr(n);
	for (auto &[x, v] : mp) {
		for (auto idx : v) {
			if (r[idx] == '1') {
				tr.modify(idx, {1, 1, 1, 1});
			} else {
				tr.modify(idx, {-inf, -inf, -inf, -inf});
			}
		}
		auto t = tr.rangeQuery(1, n);
		if (t.mx >= k) {
			cout << -x << "\n";
			return 0;
		}
	}

	cout << 0 << "\n";

    return 0;
}  
  

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 2
1 2 3 4 5
01101

output:

2

result:

ok answer is '2'

Test #2:

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

input:

5 2
3 4 5 2 1
10101

output:

0

result:

ok answer is '0'

Test #3:

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

input:

1 1
1
1

output:

1

result:

ok answer is '1'

Test #4:

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

input:

1 1
1
0

output:

0

result:

ok answer is '0'

Test #5:

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

input:

5 3
8 3 5 2 7
10101

output:

5

result:

ok answer is '5'

Test #6:

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

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: 0ms
memory: 3620kb

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: 3552kb

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: 3548kb

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: 3500kb

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: 3616kb

input:

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

output:

0

result:

ok answer is '0'

Test #12:

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

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:

97

result:

ok answer is '97'

Test #13:

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

input:

100 2
91 44 64 58 26 25 62 97 13 27 8 49 93 15 43 16 8 96 98 48 43 7 41 81 61 90 10 69 49 24 48 22 32 59 10 67 45 54 53 47 47 71 48 48 18 42 45 17 42 96 23 37 2 38 66 22 31 83 89 23 51 81 56 71 58 61 22 67 41 58 93 67 90 58 65 50 64 1 12 58 25 20 81 25 99 87 72 63 42 51 80 93 42 1 22 99 38 66 59 87
...

output:

90

result:

wrong answer expected '93', found '90'