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;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"
const int MOD = 1e9+7;
const int inf = 1e9;
const int linf = 1e18;
const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// -------------------------------------------------- Main Code --------------------------------------------------
struct bit {
int n;
vi tree;
bit(int N) {n = N+5; tree = vi(n+2);}
void update(int idx, int val) { for (idx; idx <= n; idx += (idx&-idx)) tree[idx] += val; }
int sum(int idx) { int ans = 0; for (idx; idx; idx -= (idx&-idx)) ans += tree[idx]; return ans; }
};
struct state { int l, r; };
void sol() {
int n, m; cin >> n >> m;
int req[n+1], ans[n+1];
vi positions[n+1];
for (int i = 1; i <= n; i++) ans[i] = -1;
for (int i = 1; i <= m; i++) {
int x; cin >> x;
positions[x].pb(i);
}
for (int i = 1; i <= n; i++) cin >> req[i];
int q; cin >> q;
array<int, 3> queries[q+1];
for (int i = 1; i <= q; i++) {
int a, b, c; cin >> a >> b >> c;
queries[i] = {a, b, c};
}
state currState[n+1];
for (int i = 1; i <= n; i++) currState[i] = {1, q};
int counter = n;
while (counter) {
vector<int> query[q+1];
int newCounter = 0;
for (int i = 1; i <= n; i++) {
if (currState[i].l > currState[i].r) continue;
int mid = (currState[i].l+currState[i].r)/2;
query[mid].push_back(i);
newCounter++;
}
counter = newCounter;
bit tree(m+5);
for (int i = 1; i <= q; i++) {
int l = queries[i][0], r = queries[i][1], val = queries[i][2];
if (l > r) {
swap(l, r);
tree.update(r, val);
tree.update(1, val);
tree.update(l+1, -val);
}
else {
tree.update(l, val);
tree.update(r+1, -val);
}
for (auto j : query[i]) {
int ct = 0;
for (auto x : positions[j]) {
ct += tree.sum(x);
if (ct > inf) break;
}
int &l = currState[j].l, &r = currState[j].r;
if (ct >= req[j]) r = i-1, ans[j] = i;
else l = i+1;
}
}
}
for (int i = 1; i <= n; i++) {
if (ans[i] == -1) cout << "NIE" << endl;
else cout << ans[i] << endl;
}
}
signed main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while (t--) {
sol();
}
return 0;
}
Compilation message (stderr)
met.cpp: In member function 'void bit::update(long long int, long long int)':
met.cpp:40:42: warning: statement has no effect [-Wunused-value]
40 | void update(int idx, int val) { for (idx; idx <= n; idx += (idx&-idx)) tree[idx] += val; }
| ^~~
met.cpp: In member function 'long long int bit::sum(long long int)':
met.cpp:41:42: warning: statement has no effect [-Wunused-value]
41 | int sum(int idx) { int ans = 0; for (idx; idx; idx -= (idx&-idx)) ans += tree[idx]; return ans; }
| ^~~
# | 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... |