/// tree bends in youth
/// 24 .10.2023
/// success is doing same thing in every single day!!!
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
using namespace std;
const ll N =3e5+ 5;
const ll NN =2e6 + 5;
const ll INF = -1e1;
const ll MOD = 1e9 + 7;
const ll LG = 18;
ll z[N],x[N];
ll t[4 * N],p[4 * N],c[N],b[N];
pair<ll,ll> seq[N];
set <ll> MID[N],rg[N];
ll ok[N];
void build(ll v,ll l,ll r){
p[v] = 0;
if(l == r){
t[v] = 0;
return;
}
ll mid = (l + r) / 2;
build(v+v,l,mid);
build(v+v+1,mid+1,r);
}
void push(ll v,ll l,ll r){
if(p[v]){
if(l != r){
p[v+v] += p[v];
p[v+v+1] += p[v];
}
else{
t[v] +=p[v];
}
p[v] = 0;
}
}
void upd(ll v,ll l,ll r,ll ql,ll qr,ll x){
push(v,l,r);
if(l >= ql && qr >= r){
p[v] += x;
push(v,l,r);
return;
}
if(qr < l || r < ql)return;
ll mid = (l + r) / 2;
upd(v+v,l,mid,ql,qr,x);
upd(v+v+1,mid+1,r,ql,qr,x);
}
ll get(ll v,ll l,ll r,ll x){
push(v,l,r);
if(l == r)return t[v];
ll mid = (l + r) / 2;
if(x <= mid)return get(v+v,l,mid,x);
else return get(v+v+1,mid + 1,r,x);
}
void solve(){
ll n,m;
cin >> n >> m;
for(ll i = 1;i <= m;i++){
ll u;cin >> u;
rg[u].insert(i);
}
for(ll i= 1;i <= n;i++){
cin >> b[i];
}
ll q;
cin >> q;
for(ll i = 1;i <=q;i++){
cin >> z[i] >> x[i] >> c[i];
}
for(ll i = 1;i <= n;i++){
seq[i] = {1,q};
}
ll tt = 19;
while(tt--){
for(ll i = 1;i <= n;i++){
ll md = (seq[i].F + seq[i].S) / 2;
MID[md].insert(i);
}
build(1,1,m);
for(ll i = 1;i <= q;i++){
if(z[i] > x[i]){
upd(1,1,m,1,x[i],c[i]);
upd(1,1,m,z[i],m,c[i]);
}
else{
upd(1,1,m,z[i],x[i],c[i]);
}
for(ll to : MID[i]){
ll sum= 0;
for(ll d : rg[to]){
sum += get(1,1,m,d);
}
if(sum >= b[to]){
ok[to] = 1;
seq[to].S= i;
}
else {
seq[to].F = i + 1;
}
}
}
for(ll i = 1;i <= q;i++){
MID[i].clear();
}
}
for(ll i = 1;i<=n;i++){
if(seq[i].F <= q){
cout << seq[i].F << '\n';
}
else{
cout << "NIE\n";
}
}
}
main (){
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ll abd= 1;
// cin >> abd;
for(ll i = 1;i <= abd;i++){
// cout << "Case " << i << ":\n";
solve();
}
}
/// tree bends in youth
/// 24 .10.2023
/// success is doing same thing in every single day!!!
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
using namespace std;
const ll N =3e5+ 5;
const ll NN =2e6 + 5;
const ll INF = -1e1;
const ll MOD = 1e9 + 7;
const ll LG = 18;
ll z[N],x[N];
ll t[4 * N],p[4 * N],c[N],b[N];
pair<ll,ll> seq[N];
set <ll> MID[N],rg[N];
ll ok[N];
void build(ll v,ll l,ll r){
p[v] = 0;
if(l == r){
t[v] = 0;
return;
}
ll mid = (l + r) / 2;
build(v+v,l,mid);
build(v+v+1,mid+1,r);
}
void push(ll v,ll l,ll r){
if(p[v]){
if(l != r){
p[v+v] += p[v];
p[v+v+1] += p[v];
}
else{
t[v] +=p[v];
}
p[v] = 0;
}
}
void upd(ll v,ll l,ll r,ll ql,ll qr,ll x){
push(v,l,r);
if(l >= ql && qr >= r){
p[v] += x;
push(v,l,r);
return;
}
if(qr < l || r < ql)return;
ll mid = (l + r) / 2;
upd(v+v,l,mid,ql,qr,x);
upd(v+v+1,mid+1,r,ql,qr,x);
}
ll get(ll v,ll l,ll r,ll x){
push(v,l,r);
if(l == r)return t[v];
ll mid = (l + r) / 2;
if(x <= mid)return get(v+v,l,mid,x);
else return get(v+v+1,mid + 1,r,x);
}
void solve(){
ll n,m;
cin >> n >> m;
for(ll i = 1;i <= m;i++){
ll u;cin >> u;
rg[u].insert(i);
}
for(ll i= 1;i <= n;i++){
cin >> b[i];
}
ll q;
cin >> q;
for(ll i = 1;i <=q;i++){
cin >> z[i] >> x[i] >> c[i];
}
for(ll i = 1;i <= n;i++){
seq[i] = {1,q};
}
ll tt = 19;
while(tt--){
for(ll i = 1;i <= n;i++){
ll md = (seq[i].F + seq[i].S) / 2;
MID[md].insert(i);
}
build(1,1,m);
for(ll i = 1;i <= q;i++){
if(z[i] > x[i]){
upd(1,1,m,1,x[i],c[i]);
upd(1,1,m,z[i],m,c[i]);
}
else{
upd(1,1,m,z[i],x[i],c[i]);
}
for(ll to : MID[i]){
ll sum= 0;
for(ll d : rg[to]){
sum += get(1,1,m,d);
}
if(sum >= b[to]){
ok[to] = 1;
seq[to].S= i;
}
else {
seq[to].F = i + 1;
}
}
}
for(ll i = 1;i <= q;i++){
MID[i].clear();
}
}
for(ll i = 1;i<=n;i++){
if(seq[i].F <= q){
cout << seq[i].F << '\n';
}
else{
cout << "NIE\n";
}
}
}
main (){
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ll abd= 1;
// cin >> abd;
for(ll i = 1;i <= abd;i++){
// cout << "Case " << i << ":\n";
solve();
}
}
Compilation message
met.cpp:122:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
122 | main (){
| ^~~~
met.cpp:144:10: error: redefinition of 'const long long int N'
144 | const ll N =3e5+ 5;
| ^
met.cpp:11:10: note: 'const long long int N' previously defined here
11 | const ll N =3e5+ 5;
| ^
met.cpp:145:10: error: redefinition of 'const long long int NN'
145 | const ll NN =2e6 + 5;
| ^~
met.cpp:12:10: note: 'const long long int NN' previously defined here
12 | const ll NN =2e6 + 5;
| ^~
met.cpp:146:10: error: redefinition of 'const long long int INF'
146 | const ll INF = -1e1;
| ^~~
met.cpp:13:10: note: 'const long long int INF' previously defined here
13 | const ll INF = -1e1;
| ^~~
met.cpp:147:10: error: redefinition of 'const long long int MOD'
147 | const ll MOD = 1e9 + 7;
| ^~~
met.cpp:14:10: note: 'const long long int MOD' previously defined here
14 | const ll MOD = 1e9 + 7;
| ^~~
met.cpp:148:10: error: redefinition of 'const long long int LG'
148 | const ll LG = 18;
| ^~
met.cpp:15:10: note: 'const long long int LG' previously defined here
15 | const ll LG = 18;
| ^~
met.cpp:149:4: error: redefinition of 'long long int z [300005]'
149 | ll z[N],x[N];
| ^
met.cpp:16:4: note: 'long long int z [300005]' previously declared here
16 | ll z[N],x[N];
| ^
met.cpp:149:9: error: redefinition of 'long long int x [300005]'
149 | ll z[N],x[N];
| ^
met.cpp:16:9: note: 'long long int x [300005]' previously declared here
16 | ll z[N],x[N];
| ^
met.cpp:150:4: error: redefinition of 'long long int t [1200020]'
150 | ll t[4 * N],p[4 * N],c[N],b[N];
| ^
met.cpp:17:4: note: 'long long int t [1200020]' previously declared here
17 | ll t[4 * N],p[4 * N],c[N],b[N];
| ^
met.cpp:150:13: error: redefinition of 'long long int p [1200020]'
150 | ll t[4 * N],p[4 * N],c[N],b[N];
| ^
met.cpp:17:13: note: 'long long int p [1200020]' previously declared here
17 | ll t[4 * N],p[4 * N],c[N],b[N];
| ^
met.cpp:150:22: error: redefinition of 'long long int c [300005]'
150 | ll t[4 * N],p[4 * N],c[N],b[N];
| ^
met.cpp:17:22: note: 'long long int c [300005]' previously declared here
17 | ll t[4 * N],p[4 * N],c[N],b[N];
| ^
met.cpp:150:27: error: redefinition of 'long long int b [300005]'
150 | ll t[4 * N],p[4 * N],c[N],b[N];
| ^
met.cpp:17:27: note: 'long long int b [300005]' previously declared here
17 | ll t[4 * N],p[4 * N],c[N],b[N];
| ^
met.cpp:151:13: error: redefinition of 'std::pair<long long int, long long int> seq [300005]'
151 | pair<ll,ll> seq[N];
| ^~~
met.cpp:18:13: note: 'std::pair<long long int, long long int> seq [300005]' previously defined here
18 | pair<ll,ll> seq[N];
| ^~~
met.cpp:152:10: error: redefinition of 'std::set<long long int> MID [300005]'
152 | set <ll> MID[N],rg[N];
| ^~~
met.cpp:19:10: note: 'std::set<long long int> MID [300005]' previously declared here
19 | set <ll> MID[N],rg[N];
| ^~~
met.cpp:152:17: error: redefinition of 'std::set<long long int> rg [300005]'
152 | set <ll> MID[N],rg[N];
| ^~
met.cpp:19:17: note: 'std::set<long long int> rg [300005]' previously declared here
19 | set <ll> MID[N],rg[N];
| ^~
met.cpp:153:4: error: redefinition of 'long long int ok [300005]'
153 | ll ok[N];
| ^~
met.cpp:20:4: note: 'long long int ok [300005]' previously declared here
20 | ll ok[N];
| ^~
met.cpp:154:6: error: redefinition of 'void build(long long int, long long int, long long int)'
154 | void build(ll v,ll l,ll r){
| ^~~~~
met.cpp:21:6: note: 'void build(long long int, long long int, long long int)' previously defined here
21 | void build(ll v,ll l,ll r){
| ^~~~~
met.cpp:164:6: error: redefinition of 'void push(long long int, long long int, long long int)'
164 | void push(ll v,ll l,ll r){
| ^~~~
met.cpp:31:6: note: 'void push(long long int, long long int, long long int)' previously defined here
31 | void push(ll v,ll l,ll r){
| ^~~~
met.cpp:176:6: error: redefinition of 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)'
176 | void upd(ll v,ll l,ll r,ll ql,ll qr,ll x){
| ^~~
met.cpp:43:6: note: 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)' previously defined here
43 | void upd(ll v,ll l,ll r,ll ql,ll qr,ll x){
| ^~~
met.cpp:188:4: error: redefinition of 'long long int get(long long int, long long int, long long int, long long int)'
188 | ll get(ll v,ll l,ll r,ll x){
| ^~~
met.cpp:55:4: note: 'long long int get(long long int, long long int, long long int, long long int)' previously defined here
55 | ll get(ll v,ll l,ll r,ll x){
| ^~~
met.cpp:195:6: error: redefinition of 'void solve()'
195 | void solve(){
| ^~~~~
met.cpp:62:6: note: 'void solve()' previously defined here
62 | void solve(){
| ^~~~~
met.cpp:255:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
255 | main (){
| ^~~~
met.cpp:255:1: error: redefinition of 'int main()'
met.cpp:122:1: note: 'int main()' previously defined here
122 | main (){
| ^~~~
