#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
struct BIT {
int n, n2;
vector<ll> tree;
void config(int _n) {
n = _n + 10;
n2 = _n;
tree.resize(_n+60);
}
void add(int p, int 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 clear() { for(ll &x : tree) x = 0; }
};
struct Query { int l, r, x; };
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
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);
}
int req[n+5];
for(int i=1; i<=n; i++) cin >> req[i];
int k;
cin >> k;
Query qus[k+5], q;
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);
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
2 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
2 ms |
1116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
35416 KB |
Output is correct |
2 |
Correct |
96 ms |
36720 KB |
Output is correct |
3 |
Correct |
85 ms |
36176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
86 ms |
35924 KB |
Output is correct |
2 |
Correct |
91 ms |
35924 KB |
Output is correct |
3 |
Correct |
99 ms |
36724 KB |
Output is correct |
4 |
Correct |
23 ms |
5464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
81 ms |
35272 KB |
Output is correct |
2 |
Correct |
89 ms |
36656 KB |
Output is correct |
3 |
Correct |
49 ms |
34772 KB |
Output is correct |
4 |
Correct |
97 ms |
36356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
79 ms |
35172 KB |
Output is correct |
2 |
Correct |
91 ms |
35892 KB |
Output is correct |
3 |
Correct |
66 ms |
35468 KB |
Output is correct |
4 |
Correct |
99 ms |
36948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
126 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
142 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |