This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>
struct Operation {
int64_t l, r, amt;
Operation():
l(0), r(0), amt(0) {}
Operation(int64_t l, int64_t r, int64_t amt):
l(l), r(r), amt(amt) {}
};
struct ParallelBSQuery {
int64_t color;
int64_t l, r, m;
ParallelBSQuery():
color(0), l(0), r(0), m(0) {}
ParallelBSQuery(int64_t color, int64_t l, int64_t r):
color(color), l(l), r(r), m((l+r)>>1) {}
};
int64_t x, q, ops;
int64_t color[300005];
int64_t target[300005];
int64_t ans[300005];
int64_t tree[1200005];
int64_t lazy[1200005];
std::vector<Operation> operations;
std::vector<ParallelBSQuery> queries;
std::vector<int64_t> owned_by[300005];
void push(int64_t node, int64_t l, int64_t r) {
tree[node] += lazy[node];
if (l!=r) {
lazy[node<<1] += lazy[node];
lazy[node<<1|1] += lazy[node];
}
lazy[node] = 0;
}
void update(int64_t node, int64_t l, int64_t r, int64_t st, int64_t fi, int64_t val) {
push(node,l,r);
if (l>fi||r<st) {
return;
}
if (st<=l&&r<=fi) {
lazy[node] += val;
push(node,l,r);
return;
}
int64_t m = (l+r)>>1;
update(node<<1,l,m,st,fi,val);
update(node<<1|1,m+1,r,st,fi,val);
tree[node] = tree[node<<1] + tree[node<<1|1];
}
int64_t query(int64_t node, int64_t l, int64_t r, int64_t st, int64_t fi) {
push(node,l,r);
if (l>fi||r<st) {
return 0;
}
if (st<=l&&r<=fi) {
return tree[node];
}
int64_t m = (l+r)>>1;
return query(node<<1,l,m,st,fi) + query(node<<1|1,m+1,r,st,fi);
}
int64_t get_sum(int64_t color) {
int64_t ret = 0;
for (const auto& i : owned_by[color]) {
ret += query(1,1,x,i,i);
}
return ret;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> q >> x;
for (int64_t i = 1; i <= x; i++) {
std::cin >> color[i];
owned_by[color[i]].emplace_back(i);
}
for (int64_t i = 1; i <= q; i++) {
std::cin >> target[i];
}
std::cin >> ops;
operations.reserve(ops);
for (int64_t i = 0, l, r, amt; i < ops; i++) {
std::cin >> l >> r >> amt;
operations.emplace_back(l,r,amt);
}
for (int64_t i = 0; i < q; i++) {
ans[i+1] = -1;
queries.emplace_back(i+1,0,ops-1);
}
for (int64_t iterations = 0; iterations < 19; iterations++) {
memset(tree,0,sizeof(tree));
memset(lazy,0,sizeof(lazy));
std::sort(queries.begin(),queries.end(),[](const ParallelBSQuery& a, const ParallelBSQuery& b) {
return a.m < b.m;
});
int64_t scanline = 0;
for (auto& [color, l, r, m] : queries) {
if (l>r) {
continue;
}
while (scanline<=m) {
auto [i, j, amt] = operations[scanline];
if (i>j) {
update(1,1,x,1,j,amt);
update(1,1,x,i,x,amt);
}
else {
update(1,1,x,i,j,amt);
}
++scanline;
}
int64_t cand = get_sum(color);
if (cand>=target[color]) {
ans[color] = m;
r = m-1;
}
else {
l = m+1;
}
m = (l+r)>>1;
}
}
for (int64_t i = 1; i <= q; i++) {
if (ans[i]==-1) std::cout << "NIE\n";
else std::cout << ans[i]+1 << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |