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 <bits/stdc++.h>
using namespace std;
using ll = long long;
struct st{
int l, r;
ll x;
};
template<class T>
struct BIT{
vector<T> bit;
BIT(int N) : bit(N, 0) {}
void add(int pos, T val) {
for (; pos < (int) bit.size(); pos += pos & -pos) {
bit[pos] += val;
}
}
T sum(int r) {
T res{};
for (; r > 0; r -= r & -r) {
res += bit[r];
}
return res;
}
T sum(int l, int r) { return sum(r) - sum(l - 1); }
};
vector<int> sol;
BIT<ll> bit(1);
vector<vector<int>> own;
vector<ll> v;
vector<st> q;
void add(int i, int p) {
if (q[i].l <= q[i].r) {
bit.add(q[i].l, q[i].x * p);
bit.add(q[i].r + 1, -q[i].x * p);
} else {
bit.add(1, q[i].x * p);
bit.add(q[i].r + 1, -q[i].x * p);
bit.add(q[i].l, q[i].x * p);
}
}
void solve(int lo, int hi, vector<int> const &ind) {
if (lo == hi - 1) {
vector<int> l, r;
add(lo, 1);
for (int i : ind) {
ll suma = 0;
for (int a : own[i]) {
suma += bit.sum(a);
if (suma >= v[i]) break;
}
if (suma >= v[i]) {
l.push_back(i);
} else r.push_back(i);
}
add(lo, -1);
for (int i : l) {
sol[i] = lo;
}
for (int i : r) {
sol[i] = lo + 1;
}
return;
}
int mid = (lo + hi) / 2;
for (int i = lo; i < mid; ++i) {
add(i, 1);
}
vector<int> l, r;
for (int i : ind) {
ll suma = 0;
for (int a : own[i]) {
suma += bit.sum(a);
if (suma >= v[i]) break;
}
if (suma >= v[i]) {
l.push_back(i);
} else r.push_back(i);
}
solve(mid, hi, r);
for (int i = lo; i < mid; ++i) {
add(i, -1);
}
solve(lo, mid, l);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
bit.bit.resize(n + 10);
sol.resize(n);
own.resize(n);
for (int i = 1; i <= m; ++i) {
ll a;
cin >> a;
--a;
own[a].push_back(i);
}
v.resize(n);
for (auto &a : v) cin >> a;
int k;
cin >> k;
q.resize(k);
for (int i = 0; i < k; ++i) {
cin >> q[i].l >> q[i].r >> q[i].x;
}
vector<int> tmp(n);
iota(begin(tmp), end(tmp), 0);
solve(0, k, tmp);
for (auto a : sol) {
if (a == k) {
cout << "NIE\n";
} else cout << a + 1 << '\n';
}
return 0;
}
# | 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... |