#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define int long long
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 3e5 + 2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int off = (1 << 19);
struct sgt{
int val[MAXN * 20], rs[MAXN * 20], ls[MAXN * 20], head = 1;
int version[MAXN];
int my_new(int u = 0){
val[head] = val[u];
ls[head] = ls[u];
rs[head] = rs[u];
return head++;
}
int update(int l, int r, int v, int u, int lo = 0, int hi = off){
if (r <= lo || hi <= l)
return u;
u = my_new(u);
if (l <= lo && hi <= r){
val[u] += v;
ckmin(val[u], int(1e9));
return u;
}
int mi = (lo + hi) >> 1;
ls[u] = update(l, r, v, ls[u], lo, mi);
rs[u] = update(l, r, v, rs[u], mi, hi);
return u;
}
void query(int l, int r, int v, int cur){
if (l <= r){
version[cur] = update(l, r + 1, v, version[cur - 1]);
} else {
version[cur] = update(l, off, v, version[cur - 1]);
version[cur] = update(0, r + 1, v, version[cur]);
}
}
int get(int pos, int u, int lo = 0, int hi = off){
if (pos >= hi || pos < lo)
return 0;
if (!u) return 0;
int mi = (lo + hi) >> 1;
if (pos < mi)
return val[u] + get(pos, ls[u], lo, mi);
else
return val[u] + get(pos, rs[u], mi, hi);
}
} seg;
struct postions {
int head[MAXN], next[MAXN], val[MAXN], tot = 1;
void add(int num, int pos){
next[tot] = head[num];
val[tot] = pos;
head[num] = tot;
tot++;
}
} pos;
int need[MAXN];
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++){
int x;
cin >> x;
pos.add(x, i);
}
for (int i = 1; i <= n; i++){
cin >> need[i];
}
int q;
cin >> q;
for (int i = 1; i <= q; i++){
int l, r, v;
cin >> l >> r >> v;
seg.query(l, r, v, i);
}
for (int i = 1; i <= n; i++){
int lo = 0, hi = q + 1;
while (hi - lo > 1){
int mi = (lo + hi) >> 1;
int sum = 0;
for (int idx = pos.head[i]; idx; idx = pos.next[idx]){
int cur = pos.val[idx];
sum += seg.get(cur, seg.version[mi]);
ckmin(sum, int(1e9));
}
if (sum >= need[i])
hi = mi;
else
lo = mi;
}
if (hi != q + 1)
cout << hi << endl;
else
cout << "NIE\n";
}
}
Compilation message
met.cpp: In member function 'long long int sgt::update(long long int, long long int, long long int, long long int, long long int, long long int)':
met.cpp:16:13: error: expected primary-expression before 'long'
16 | #define int long long
| ^~~~
met.cpp:39:18: note: in expansion of macro 'int'
39 | ckmin(val[u], int(1e9));
| ^~~
met.cpp: In function 'int32_t main()':
met.cpp:16:13: error: expected primary-expression before 'long'
16 | #define int long long
| ^~~~
met.cpp:105:16: note: in expansion of macro 'int'
105 | ckmin(sum, int(1e9));
| ^~~
