#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
#define pf push_front
#define F first
#define S second
#define IShowSpeed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define all(a) a.begin(),a.end()
const int N=3e5+10;
const int mod=1e9+7;
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};
ll a[N],b[N],l[N],r[N],x[N],L[N],R[N],mi[N],t[4*N],md[4*N],ans[N];
vector<ll>g[N],mids[N];
void ah(ll* x) {
x = min(mod,x);
return;
}
void push(ll v, ll tl, ll tr) {
if(tl != tr && md[v]) {
ll mid = (tl + tr) >> 1;
md[v+v] += md[v];
md[v+v+1] += md[v];
t[v+v] += md[v];
t[v+v+1] += md[v];
ah(md[v+v]);
ah(md[v+v+1]);
ah(t[v+v]);
ah(t[v+v+1]);
}
md[v] = 0;
}
void upd(ll v, ll tl, ll tr, ll l, ll r, ll x) {
if(l > tr || tl > r) return;
push(v,tl,tr);
if(l <= tl && tr <= r) {
md[v] += x;
t[v] += md[v];
ah(md[v]);
ah(t[v]);
push(v,tl,tr);
return;
}
ll mid = (tl + tr) >> 1;
upd(v+v,tl,mid,l,r,x);
upd(v+v+1,mid+1,tr,l,r,x);
}
ll get(ll v, ll tl, ll tr, ll pos) {
if(tl == tr) return t[v];
push(v,tl,tr);
ll mid = (tl + tr) >> 1;
if(pos <= mid) return get(v+v,tl,mid,pos);
else return get(v+v+1,mid+1,tr,pos);
}
int main()
{
IShowSpeed
ll tt=1;
//cin>>tt;
while(tt--)
{
ll n,m,q;
cin>>n>>m;
for(int i=1;i<=m;i++) {
cin>>a[i];
g[a[i]].pb(i);
}
for(int i=1;i<=n;i++) cin>>b[i];
cin>>q;
for(int i=1;i<=q;i++) cin>>l[i]>>r[i]>>x[i];
for(int i=1;i<=n;i++) {
L[i] = 1;
R[i] = q;
mi[i] = (q+1) >> 1;
}
while(true) {
bool chk = 0;
for(int i=1;i<=m*4;i++) t[i] = md[i] = 0;
for(int i=1;i<=q;i++) mids[i].clear();
for(int i=1;i<=n;i++) {
if(L[i] <= R[i]) {
chk = 1;
mi[i] = (L[i] + R[i]) >> 1;
mids[mi[i]].pb(i);
}
}
if(!chk) break;
for(int i=1;i<=q;i++) {
if(l[i] <= r[i]) upd(1,1,m,l[i],r[i],x[i]);
else {
upd(1,1,m,l[i],m,x[i]);
upd(1,1,m,1,r[i],x[i]);
}
for(ll ok: mids[i]) {
ll sum = 0;
for(ll y: g[ok]) {
sum += get(1,1,m,y);
if(sum >= b[ok]) break;
}
if(sum >= b[ok]) ans[ok] = i,R[ok] = i - 1;
else L[ok] = i + 1;
}
}
}
for(int i=1;i<=n;i++) {
if(!ans[i]) cout<<"NIE\n";
else cout<<ans[i]<<"\n";
}
}
}
/*
*/
Compilation message (stderr)
met.cpp: In function 'void ah(int*)':
met.cpp:18:16: error: no matching function for call to 'min(const int&, int*&)'
18 | x = min(mod,x);
| ~~~^~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
from /usr/include/c++/11/cmath:1935,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
from met.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
met.cpp:18:16: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'int*')
18 | x = min(mod,x);
| ~~~^~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
from /usr/include/c++/11/cmath:1935,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
from met.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
met.cpp:18:16: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'int*')
18 | x = min(mod,x);
| ~~~^~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
from met.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3449 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: template argument deduction/substitution failed:
met.cpp:18:16: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
18 | x = min(mod,x);
| ~~~^~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
from met.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3455 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: template argument deduction/substitution failed:
met.cpp:18:16: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
18 | x = min(mod,x);
| ~~~^~~~~~~
met.cpp: In function 'void push(int, int, int)':
met.cpp:29:26: error: invalid conversion from 'int' to 'int*' [-fpermissive]
29 | ah(md[v+v]);
| ~~~~~~^
| |
| int
met.cpp:17:13: note: initializing argument 1 of 'void ah(int*)'
17 | void ah(ll* x) {
| ^
met.cpp:30:28: error: invalid conversion from 'int' to 'int*' [-fpermissive]
30 | ah(md[v+v+1]);
| ~~~~~~~~^
| |
| int
met.cpp:17:13: note: initializing argument 1 of 'void ah(int*)'
17 | void ah(ll* x) {
| ^
met.cpp:31:25: error: invalid conversion from 'int' to 'int*' [-fpermissive]
31 | ah(t[v+v]);
| ~~~~~^
| |
| int
met.cpp:17:13: note: initializing argument 1 of 'void ah(int*)'
17 | void ah(ll* x) {
| ^
met.cpp:32:27: error: invalid conversion from 'int' to 'int*' [-fpermissive]
32 | ah(t[v+v+1]);
| ~~~~~~~^
| |
| int
met.cpp:17:13: note: initializing argument 1 of 'void ah(int*)'
17 | void ah(ll* x) {
| ^
met.cpp: In function 'void upd(int, int, int, int, int, int)':
met.cpp:43:24: error: invalid conversion from 'int' to 'int*' [-fpermissive]
43 | ah(md[v]);
| ~~~~^
| |
| int
met.cpp:17:13: note: initializing argument 1 of 'void ah(int*)'
17 | void ah(ll* x) {
| ^
met.cpp:44:23: error: invalid conversion from 'int' to 'int*' [-fpermissive]
44 | ah(t[v]);
| ~~~^
| |
| int
met.cpp:17:13: note: initializing argument 1 of 'void ah(int*)'
17 | void ah(ll* x) {
| ^