/// 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;
int z[N],x[N],c[N];
ll t[4 * N],p[4 * N],b[N];
pair<int,int> seq[N];
set <int> MID[N],rg[N];
int ok[N];
void build(int v,int l,int r){
p[v] = 0;
if(l == r){
t[v] = 0;
return;
}
int mid = (l + r) / 2;
build(v+v,l,mid);
build(v+v+1,mid+1,r);
}
void push(int v,int l,int r){
if(p[v] > 0){
if(l != r){
p[v+v] += p[v];
p[v+v+1] += p[v];
}
else{
t[v] +=p[v];
}
p[v] = 0;
}
}
void upd(int v,int l,int r,int ql,int qr,int x){
push(v,l,r);
if(l >= ql && qr >= r){
p[v] += x;
push(v,l,r);
return;
}
if(qr < l || r < ql)return;
int mid = (l + r) / 2;
upd(v+v,l,mid,ql,qr,x);
upd(v+v+1,mid+1,r,ql,qr,x);
}
ll get(int v,int l,int r,int x){
push(v,l,r);
if(l == r)return t[v];
int 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(){
int n,m;
cin >> n >> m;
for(int i = 1;i <= m;i++){
int u;cin >> u;
rg[u].insert(i);
}
for(int i= 1;i <= n;i++){
cin >> b[i];
}
int q;
cin >> q;
for(int i = 1;i <=q;i++){
cin >> z[i] >> x[i] >> c[i];
}
for(int i = 1;i <= n;i++){
seq[i] = {1,q};
}
int tt = 19;
while(tt--){
for(int i = 1;i <= n;i++){
int md = (seq[i].F + seq[i].S) / 2;
MID[md].insert(i);
}
build(1,1,m);
for(int 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(int to : MID[i]){
ll sum= 0;
for(int d : rg[to]){
sum += get(1,1,m,d);
if(sum >= b[to])break;
}
if(sum >= b[to]){
ok[to] = 1;
seq[to].S= i;
}
else {
seq[to].F = i + 1;
}
}
}
for(int i = 1;i <= q;i++){
MID[i].clear();
}
}
for(int 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:123:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
123 | main (){
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
41552 KB |
Output is correct |
| 2 |
Correct |
15 ms |
41564 KB |
Output is correct |
| 3 |
Correct |
17 ms |
41560 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
41576 KB |
Output is correct |
| 2 |
Correct |
13 ms |
41452 KB |
Output is correct |
| 3 |
Correct |
16 ms |
41596 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
433 ms |
46116 KB |
Output is correct |
| 2 |
Correct |
655 ms |
47160 KB |
Output is correct |
| 3 |
Correct |
621 ms |
46536 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
561 ms |
46340 KB |
Output is correct |
| 2 |
Correct |
610 ms |
46172 KB |
Output is correct |
| 3 |
Correct |
655 ms |
47152 KB |
Output is correct |
| 4 |
Correct |
141 ms |
46676 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
241 ms |
46164 KB |
Output is correct |
| 2 |
Correct |
467 ms |
47152 KB |
Output is correct |
| 3 |
Correct |
236 ms |
41524 KB |
Output is correct |
| 4 |
Correct |
571 ms |
46736 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
477 ms |
45904 KB |
Output is correct |
| 2 |
Correct |
450 ms |
46396 KB |
Output is correct |
| 3 |
Correct |
482 ms |
45980 KB |
Output is correct |
| 4 |
Correct |
565 ms |
47156 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
166 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
144 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
