Submission #748272

#TimeUsernameProblemLanguageResultExecution timeMemory
748272jamezzzMeteors (POI11_met)C++17
0 / 100
832 ms35912 KiB
#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 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...