Submission #743788

#TimeUsernameProblemLanguageResultExecution timeMemory
743788jamezzzTortoise (CEOI21_tortoise)C++17
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #define dbg(...) printf(__VA_ARGS__); #define getchar_unlocked getchar #else #define dbg(...) #endif #define sf scanf #define pf printf #define fi first #define se second #define pb push_back #define psf push_front #define ppb pop_back #define ppf pop_front #define sz(x) (int)x.size() #define mnto(x,y) x=min(x,(__typeof__(x))y) #define mxto(x,y) x=max(x,(__typeof__(x))y) #define INF 1023456789 #define LINF 1023456789123456789 #define all(x) x.begin(),x.end() #define lb(x,v) (lower_bound(all(x),v)-x.begin()) #define ub(x,v) (upper_bound(all(x),v)-x.begin()) #define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin()); typedef long long ll; typedef long double ld; typedef pair<int,int> ii; typedef pair<ll,ll> pll; typedef tuple<int,int,int> iii; typedef tuple<int,int,int,int> iiii; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; mt19937 rng(time(0)); #define mod 1000000007 inline int add(int a,int b){ int r=a+b; while(r>=mod)r-=mod; while(r<0)r+=mod; return r; } inline int mult(int a,int b){ return (int)(((ll)(a*b))%mod); } inline int rd(){ int x=0; char ch=getchar_unlocked(); while(!(ch&16))ch=getchar_unlocked();//keep reading while current character is whitespace while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered x=(x<<3)+(x<<1)+(ch&15); ch=getchar_unlocked(); } return x; } #define maxn 500005 struct node{ int s,e,m,v,lz; node *l,*r; node(int _s,int _e){ s=_s,e=_e,m=(s+e)>>1,v=0,lz=0; if(s!=e)l=new node(s,m),r=new node(m+1,e); } void ppo(){ v+=lz; if(s!=e&&lz)l->lz+=lz,r->lz+=lz; lz=0; } void up(int x,int y,int nv){ if(s==x&&e==y){lz+=nv;return;} if(y<=m)l->up(x,y,nv); else if(x>m)r->up(x,y,nv); else l->up(x,m,nv),r->up(m+1,y,nv); l->ppo(),r->ppo(); v=min(l->v,r->v); } int qry(int x,int y){ ppo(); if(s==x&&e==y)return v; if(y<=m)return l->qry(x,y); if(x>m)return r->qry(x,y); return min(l->qry(x,m),r->qry(m+1,y)); } }*rt; int n,a[maxn],d[maxn],mx[maxn]; set<ii> s; ll ans; vi play,shop; int main(){ sf("%d",&n); rt=new node(1,n); for(int i=1;i<=n;++i){ sf("%d",&a[i]); if(a[i]==-1){ play.pb(i); rt->up(i,i,INF); } else{ shop.pb(i); ans+=a[i]; rt->up(i,i,2*i); } } int ptr=-1; for(int i=0;i<sz(shop);++i){ while(ptr+1<sz(play)&&play[ptr+1]<shop[i])++ptr; int x=shop[i]; d[x]=INF; if(ptr!=-1)d[x]=min(d[x],shop[i]-play[ptr]); if(ptr+1<sz(play))d[x]=min(d[x],play[ptr+1]-shop[i]); if(d[i]>d[mx[ptr]])mx[ptr]=i; s.insert({d[x],x}); } for(int i=0;i<sz(play)-1;++i){ rt->up(play[i+1],n,-play[i+1]+play[i]); if(mx[i]==0)continue; int x=shop[mx[ptr]]; --ans;--a[x]; if(a[x]==0)s.erase(s.find({d[x],x})); } while(!s.empty()){ auto[_,i]=*s.begin(); //printf("now: %d\n",i); int mn=rt->qry(i,n); int num=min(a[i],mn/(2*d[i])); //printf("mn=%d, num=%d\n",mn,num); ans-=num; rt->up(i,n,-num*d[i]*2); s.erase(s.begin()); //for(int i=1;i<=n;++i)printf("%d ",rt->qry(i,i)); //printf("\n"); } pf("%lld\n",ans); }

Compilation message (stderr)

tortoise.cpp: In function 'int main()':
tortoise.cpp:99:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  sf("%d",&n);
      |    ^
tortoise.cpp:102:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   sf("%d",&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...