This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define INF 1023456789
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
struct query{ int s,e;vi v; };
queue<query> q;
int n,m,o,p[300005],k,l[300005],r[300005],a[300005],ans[300005];
ll ft[300005];
vi s[300005];
void up(int x,int v){
while(x<=m){
ft[x]+=v;
ft[x]=max(ft[x],(ll)INF);
x+=x&-x;
}
}
ll qry(int x){
ll res=0;
while(x)res+=ft[x],x-=x&-x;
return res;
}
int main(){
sf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
sf("%d",&o);
s[o].pb(i);
}
for(int i=1;i<=n;++i)sf("%d",&p[i]);
sf("%d",&k);
for(int i=1;i<=k;++i){
sf("%d%d%d",&l[i],&r[i],&a[i]);
}
l[k+1]=1;r[k+1]=m;a[k+1]=1e9;
query x={1,k+1};
for(int i=1;i<=n;++i)x.v.pb(i);
q.push(x);
int pv=0;
while(!q.empty()){
query x={0,0};
swap(x,q.front());
q.pop();
if(x.s==x.e){
for(int i:x.v)ans[i]=x.s;
continue;
}
int md=(x.s+x.e)/2;
query nl={x.s,md},nr={md+1,x.e};
if(md<pv)memset(ft,0,sizeof ft),pv=0;
while(pv!=md){
++pv;
if(l[pv]<=r[pv]){
up(l[pv],a[pv]);
up(r[pv]+1,-a[pv]);
}
else{
up(1,a[pv]);
up(r[pv]+1,-a[pv]);
up(l[pv],a[pv]);
}
}
for(int i:x.v){
ll tot=0;
for(int j:s[i])tot+=qry(j);
if(tot>=p[i])nl.v.pb(i);
else nr.v.pb(i);
}
q.push(nl);q.push(nr);
}
for(int i=1;i<=n;++i){
if(ans[i]<=k)pf("%d\n",ans[i]);
else pf("NIE\n");
}
}
Compilation message (stderr)
met.cpp: In function 'int main()':
met.cpp:36:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | sf("%d%d",&n,&m);
| ^
met.cpp:38:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | sf("%d",&o);
| ^
met.cpp:41:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | for(int i=1;i<=n;++i)sf("%d",&p[i]);
| ^
met.cpp:42:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | sf("%d",&k);
| ^
met.cpp:44:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | sf("%d%d%d",&l[i],&r[i],&a[i]);
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |