Submission #748288

#TimeUsernameProblemLanguageResultExecution timeMemory
748288jamezzzMeteors (POI11_met)C++17
100 / 100
3336 ms50560 KiB
#include <bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define pb push_back #define INF 1023456789 typedef long long ll; typedef vector<int> vi; #define maxn 300005 ll seg[maxn<<3]; void reset(int i,int s,int e){ seg[i]=0; if(s!=e){ int m=(s+e)>>1; reset(2*i+1,s,m); reset(2*i+2,m+1,e); } } void up(int i,int s,int e,int x,int y,int v){ if(s==x&&e==y){seg[i]+=v;return;} int m=(s+e)>>1; if(y<=m)up(2*i+1,s,m,x,y,v); else if(x>m)up(2*i+2,m+1,e,x,y,v); else up(2*i+1,s,m,x,m,v),up(2*i+2,m+1,e,m+1,y,v); } ll qry(int i,int s,int e,int x){ if(s==x&&e==x)return seg[i]; int m=(s+e)>>1; if(x<=m)return seg[i]+qry(2*i+1,s,m,x); else return seg[i]+qry(2*i+2,m+1,e,x); } int n,m,p[maxn],k,l[maxn],r[maxn],a[maxn],ans[maxn]; vi s[maxn]; int main(){ sf("%d%d",&n,&m); for(int i=1;i<=m;++i){ int o;sf("%d",&o); s[o].pb(i); } vi v; for(int i=1;i<=n;++i){ sf("%d",&p[i]); v.pb(i); ans[i]=-1; } sf("%d",&k); for(int i=1;i<=k;++i)sf("%d%d%d",&l[i],&r[i],&a[i]); queue<tuple<int,int,vi>> q; q.push({1,k,v}); int pv=0; while(!q.empty()){ auto[lo,hi,v]=q.front(); q.pop(); if(lo>hi||v.empty())continue; int mid=(lo+hi)>>1; if(mid<pv)reset(0,1,m),pv=0; while(pv<mid){ ++pv; if(l[pv]<=r[pv])up(0,1,m,l[pv],r[pv],a[pv]); else{ up(0,1,m,l[pv],m,a[pv]); up(0,1,m,1,r[pv],a[pv]); } } vi lv,rv; for(int x:v){ ll tot=0; for(int i:s[x]){ tot+=qry(0,1,m,i); if(tot>=p[x])break; } if(tot>=p[x])lv.pb(x),ans[x]=mid; else rv.pb(x); } q.push({lo,mid-1,lv}); q.push({mid+1,hi,rv}); } for(int i=1;i<=n;++i){ if(ans[i]==-1)pf("NIE\n"); else pf("%d\n",ans[i]); } }

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:41:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  sf("%d%d",&n,&m);
      |    ^
met.cpp:43:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   int o;sf("%d",&o);
      |           ^
met.cpp:48:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   sf("%d",&p[i]);
      |     ^
met.cpp:52:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  sf("%d",&k);
      |    ^
met.cpp:53:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  for(int i=1;i<=k;++i)sf("%d%d%d",&l[i],&r[i],&a[i]);
      |                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...