#include <bits/stdc++.h>
using namespace std;
void main_program();
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
main_program();
}
#define int long long
struct Segtree{
vector<int> tree;
int _n;
Segtree(int N): tree(4*N, 0), _n(N) {}
void update(int tl, int tr, int delta) { update(1, 0, _n - 1, tl, tr, delta); }
void update(int i, int l, int r, int tl, int tr, int delta){
if (tl <= l && r <= tr) tree[i] += delta;
else if (tl > r || tr < l) {}
else{
int mid = (l + r) >> 1;
update(i<<1, l, mid, tl, tr, delta);
update(i<<1|1, mid+1, r, tl, tr, delta);
}
}
int get(int pos) { return get(1, 0, _n - 1, pos); }
int get(int i, int l, int r, int pos){
if (l == pos && r == pos) return tree[i];
int mid = (l + r) >> 1;
if (pos <= mid) return tree[i] + get(i<<1, l, mid, pos);
else return tree[i] + get(i<<1|1, mid+1, r, pos);
}
};
struct Query{
int l, r, c;
};
struct ParallelBinarySearch{
int l, r;
vector<int> q;
ParallelBinarySearch(int L, int R): l(L), r(R) {}
};
int N, M, Q;
vector<int> res, d;
vector<vector<int>> houses;
vector<Query> qs;
void main_program(){
cin >> M >> N;
res.assign(M, 0);
d.resize(M);
houses.resize(M);
for (int i = 0; i < N; i++){
int x; cin >> x; x--;
houses[x].push_back(i);
}
for (int i = 0; i < M; i++){
cin >> d[i];
}
cin >> Q;
qs.resize(Q);
for (int i = 0; i < Q; i++){
int l, r, c; cin >> l >> r >> c; l--; r--;
qs[i] = Query{l, r, c};
}
vector<ParallelBinarySearch> pbs;
pbs.emplace_back(0, Q);
pbs[0].q.resize(M);
iota(pbs[0].q.begin(), pbs[0].q.end(), 0);
while (!pbs.empty()){
Segtree st(N);
vector<ParallelBinarySearch> newpbs;
int crr = -1;
// DEBUG //
// for (auto range: pbs){
// cout << range.l << " -> " << range.r << ":";
// for (auto i: range.q) cout << " " << i;
// cout << "\n";
// }
// DEBUG //
for (auto range: pbs){
if (range.l == range.r){
for (auto i: range.q) res[i] = range.l;
continue;
}
int mid = (range.l + range.r) >> 1;
ParallelBinarySearch leftnode(range.l, mid), rightnode(mid+1, range.r);
while (crr < mid){
crr++;
int ql = qs[crr].l, qr = qs[crr].r, qc = qs[crr].c;
if (ql <= qr) st.update(ql, qr, qc);
else{
st.update(ql, N-1, qc); st.update(0, qr, qc);
}
// DEBUG //
// cout << "crr: " << crr << "\n";
// for (int i = 0; i < N; i++) cout << st.get(i) << " \n"[i == N-1];
// DEBUG //
}
for (auto i: range.q){
int total = 0;
for (auto j: houses[i]){
total += st.get(j);
}
if (total >= d[i]) leftnode.q.push_back(i);
else rightnode.q.push_back(i);
}
if (!leftnode.q.empty()) newpbs.push_back(leftnode);
if (!rightnode.q.empty()) newpbs.push_back(rightnode);
}
pbs.swap(newpbs);
}
for (int i = 0; i < M; i++){
if (res[i] == Q) cout << "vze\n";
else cout << res[i] + 1 << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
253 ms |
4040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
310 ms |
5620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
134 ms |
4776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
3628 KB |
Output is correct |
| 2 |
Incorrect |
279 ms |
5484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3107 ms |
30464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2951 ms |
29452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
