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>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
void setIO() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
struct BIT {
int n, n2;
vector<ll> tree, val;
void config(int _n) {
n = _n + 10;
n2 = _n;
tree.resize(_n+60);
val.resize(_n+60);
}
void add(int p, int v) {
val[p] += v;
for(p++; p<n; p+=p&-p) tree[p] += v;
}
ll query(int p) {
ll ans = 0;
for(p++; p>0; p-=p&-p) ans += tree[p];
return ans;
}
ll sum(int l, int r) { return query(r) - query(l-1); }
void set(int p, int v) { add(p, v - val[p]); }
void clear() {
for(ll &x : tree) x = 0;
for(ll &x : val) x = 0;
}
};
struct Query { int l, r, x; };
int32_t main() {
setIO();
int n, m;
cin >> n >> m;
vector<vector<int> > owner(n+5);
for(int i=1; i<=m; i++) {
int x;
cin >> x;
owner[x].push_back(i);
}
vector<ll> req(n+5);
for(int i=1; i<=n; i++) cin >> req[i];
int k;
cin >> k;
vector<Query> qus(k+5);
for(int i=1; i<=k; i++)
cin >> qus[i].l >> qus[i].r >> qus[i].x;
vector<int> L(n+5, 1), R(n+5, k+1);
bool changed = true;
BIT bit;
bit.config(m+1);
vector<stack<int> > to_check(k+5);
Query q;
while(changed) {
changed = false;
bit.clear();
for(int i=1; i<=n; i++)
if(L[i] != R[i]) to_check[(L[i]+R[i])/2].push(i);
for(int it=1; it<=k; it++) {
q = qus[it];
if(q.l <= q.r) {
bit.add(q.l, q.x);
bit.add(q.r+1, -q.x);
} else {
bit.add(q.l, q.x);
bit.add(m+1, -q.x);
bit.add(1, q.x);
bit.add(q.r+1, -q.x);
}
while(!to_check[it].empty()) {
changed = true;
int u = to_check[it].top();
to_check[it].pop();
ll total = 0;
for(int &x : owner[u]) {
total += bit.query(x);
if(total > req[u]) break;
}
if(total >= req[u]) R[u] = it;
else L[u] = it + 1;
}
}
}
for(int i=1; i<=n; i++) {
if(L[i] <= k) cout << L[i] << '\n';
else cout << "NIE\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... |