//meteors
#include <bits/stdc++.h>
using namespace std;
vector<long long int> st;
vector<int> l;
vector<int> r;
vector<int> place[300100];
int N,M,h;
int it;
int k;
int root[300100];
int g[300100];
void update(int i, int s, int e, int S, int E, int c, int k){
if(S <= E){
if(S <= s && e <= E){
st.push_back(st[c] + k);
l.push_back(l[c]);
r.push_back(r[c]);
it++;
return;
}
st.push_back(st[c]);
l.push_back(0);
r.push_back(0);
it++;
int m = (s + e)/2;
int lef = l[c];
int righ = r[c];
if(S <= m){
lef = it;
update(it, s, m, S, E, l[c], k);
}
if(E > m){
righ = it;
update(it,m + 1,e, S, E,r[c],k);
}
l[i] = lef;
r[i] = righ;
return;
}
else{
if(S <= s || e <= E){
st.push_back(st[c] + k);
l.push_back(l[c]);
r.push_back(r[c]);
it++;
return;
}
st.push_back(st[c]);
l.push_back(0);
r.push_back(0);
it++;
int m = (s + e)/2;
int lef = l[c];
int righ = r[c];
if(S <= m || s <= E){
lef = it;
update(it, s, m, S, E, l[c], k);
}
if(m < E || S <= e){
righ = it;
update(it,m + 1,e, S, E,r[c],k);
}
l[i] = lef;
r[i] = righ;
return;
}
}
long long int query(int i, int s, int e, int in){
if(s == e){
return st[i];
}
if(in <= (s+e)/2){
return st[i] + query(l[i], s, (s+e)/2,in);
}
else{
return st[i] + query(r[i],(s+e)/2+1,e,in);
}
}
int main(){
scanf(" %d",&N);
scanf(" %d",&M);
for(int i = 1; i <= M; i++){
scanf(" %d",&h);
place[h].push_back(i);
}
for(int i = 1; i <= N; i++){
scanf(" %d",&g[i]);
}
it = 0;
st.push_back(0);
l.push_back(0);
r.push_back(0);
it++;
scanf(" %d",&k);
root[0] = 0;
for(int i = 1; i <= k ; i++){
int s,e,a;
scanf(" %d",&s);
scanf(" %d",&e);
scanf(" %d",&a);
root[i] = it;
update(it, 1, M, s, e, root[i - 1], a);
}
for(int i = 1; i <= N; i++){
int s = 1;
int e = k + 1;
int m;
while(s != e){
m = (s+e)/2;
long long int some = 0;
for(int j : place[i]){
some += query(root[m],1,M,j);
}
if(some >= g[i]){
e = m;
}
else{
s = m + 1;
}
}
if(s == k + 1){
printf("NIE\n");
}
else{
printf("%d\n",s);
}
}
/*for(int j = 0; j <= k; j++){
for(int i = 1; i <= M; i++){
printf("%lld ",query(root[j],1,M,i));
}
printf("\n");
}*/
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf(" %d",&N);
| ~~~~~^~~~~~~~~~
met.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | scanf(" %d",&M);
| ~~~~~^~~~~~~~~~
met.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf(" %d",&h);
| ~~~~~^~~~~~~~~~
met.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf(" %d",&g[i]);
| ~~~~~^~~~~~~~~~~~~
met.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | scanf(" %d",&k);
| ~~~~~^~~~~~~~~~
met.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
122 | scanf(" %d",&s);
| ~~~~~^~~~~~~~~~
met.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | scanf(" %d",&e);
| ~~~~~^~~~~~~~~~
met.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
124 | scanf(" %d",&a);
| ~~~~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
7892 KB |
Output is correct |
| 2 |
Correct |
7 ms |
8020 KB |
Output is correct |
| 3 |
Correct |
7 ms |
8020 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8020 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8020 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
138 ms |
50664 KB |
Output is correct |
| 2 |
Correct |
206 ms |
63608 KB |
Output is correct |
| 3 |
Correct |
323 ms |
45816 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
162 ms |
50828 KB |
Output is correct |
| 2 |
Correct |
214 ms |
45616 KB |
Output is correct |
| 3 |
Correct |
213 ms |
63572 KB |
Output is correct |
| 4 |
Correct |
46 ms |
11716 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
101 ms |
38044 KB |
Output is correct |
| 2 |
Correct |
117 ms |
43404 KB |
Output is correct |
| 3 |
Correct |
56 ms |
35408 KB |
Output is correct |
| 4 |
Correct |
235 ms |
45912 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
146 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
167 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
224 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
