// KCPC - 50.6907
#include <bits/stdc++.h>
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define md(l, r) ((l + r) >> 1)
#define rv(x) ((x << 1) + 1)
#define lv(x) (x << 1)
#define pb emplace_back
#define elif else if
#define uns unsigned
#define emp empty()
#define nll nullptr
#define S second
#define F first
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef vector < ll > vll;
typedef vector < int > vi;
typedef pair < ll, ll > pll;
typedef pair < int, int > pi;
typedef pair < ldb, ldb > pldb;
typedef vector < pair < ll, ll > > vpll;
typedef vector < pair < int, int > > vpi;
const int N = 3e5 + 3;
const int M = 1e4 + 123;
const int mod = 1e9 + 7;
const int mxlg = 19;
const int K = 20;
const int P = 31;
const ll inf = 1e9 + 10;
//mt19937 rnd(07062006);
int n, m, q;
ll s;
int a[N], b[N], l[N], r[N], x[N];
int al[N], ar[N];
ll t[4 * N];
vii v[N], vq[N];
void upd(ll tl, ll tr, ll x, ll v = 1, ll l = 1, ll r = m){
if(r < tl || tr < l) return;
if(tl <= l && r <= tr){
t[v] += x;
return;
}
ll m = md(l, r);
upd(tl, tr, x, lv(v), l, m);
upd(tl, tr, x, rv(v), m + 1, r);
}
ll get(ll k, ll v = 1, ll l = 1, ll r = m){
if(l == r) return t[v];
ll m = md(l, r);
if(k <= m) return get(k, lv(v), l, m) + t[v];
else return get(k, rv(v), m + 1, r) + t[v];
}
void output(){
cin >> n >> m;
for(int i = 1; i <= m; i++) cin >> b[i], v[b[i]].pb(i);
for(int i = 1; i <= n; i++) cin >> a[i];
cin >> q;
for(int i = 1; i <= n; i++){
al[i] = 1;
ar[i] = q + 1;
}
for(int i = 1; i <= q; i++) cin >> l[i] >> r[i] >> x[i];
bool ok = 1;
while(ok){
ok = 0;
memset(t, 0, sizeof(t));
for(int i = 1; i <= n; i++)
if(al[i] != ar[i])
vq[md(al[i], ar[i])].pb(i);
for(int i = 1; i <= q; i++){
if(l[i] <= r[i]) upd(l[i], r[i], x[i]);
else upd(l[i], m, x[i]), upd(1, r[i], x[i]);
for(auto id : vq[i]){
ok = 1, s = 0;
for(auto x : v[id]){
s += get(x);
if(s >= a[id]) break;
}
if(s >= a[id]) ar[id] = i;
else al[id] = i + 1;
}
vq[i].clear();
}
}
for(int i = 1; i <= n; i++){
if(al[i] == q + 1) cout << "NIE\n";
else cout << al[i] << '\n';
}
}
const bool cases = 0;
signed main(){
// file("disrupt");
adiyer();
int tt = 1;
if(cases) cin >> tt;
for(int i = 1; i <= tt; i++){
// cout << "Case " << i << ":\n";
output();
}
}
Compilation message
met.cpp:46:1: error: 'vii' does not name a type; did you mean 'vpi'?
46 | vii v[N], vq[N];
| ^~~
| vpi
met.cpp: In function 'void output()':
met.cpp:68:43: error: 'v' was not declared in this scope
68 | for(int i = 1; i <= m; i++) cin >> b[i], v[b[i]].pb(i);
| ^
met.cpp:82:5: error: 'vq' was not declared in this scope; did you mean 'q'?
82 | vq[md(al[i], ar[i])].pb(i);
| ^~
| q
met.cpp:86:18: error: 'vq' was not declared in this scope; did you mean 'q'?
86 | for(auto id : vq[i]){
| ^~
| q
met.cpp:88:18: error: 'v' was not declared in this scope
88 | for(auto x : v[id]){
| ^
met.cpp:95:4: error: 'vq' was not declared in this scope; did you mean 'q'?
95 | vq[i].clear();
| ^~
| q
