Submission #824111

#TimeUsernameProblemLanguageResultExecution timeMemory
824111alvingogoThe short shank; Redemption (BOI21_prison)C++14
70 / 100
72 ms36540 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #define AquA cin.tie(0);ios_base::sync_with_stdio(0); #define fs first #define sc second #define p_q priority_queue #define int long long using namespace std; struct no{ vector<int> ch; int dep=-1,dp=0; }; vector<no> g; void dfs(int r,int f){ g[r].dep=g[f].dep+1; g[r].dp=g[r].dep; for(auto h:g[r].ch){ dfs(h,r); g[r].dp=max(g[r].dp,g[h].dp); } } vector<int> z; void dfs2(int r,int f,int y){ pair<int,int> mx(-1,-1); for(auto h:g[r].ch){ mx=max(mx,{g[h].dp,h}); } for(auto h:g[r].ch){ if(mx.sc==h){ dfs2(h,r,y+1); } else{ dfs2(h,r,1); } } if(mx.sc==-1){ z.push_back(y); } } signed main(){ AquA; int n,d,t; cin >> n >> d >> t; g.resize(n+1); vector<int> v(n); int l=0,ff=0; for(int i=0;i<n;i++){ cin >> v[i]; if(v[i]>t && ff==0){ l++; } else{ ff=1; } } int rt=n; int rn=2e9; vector<int> s; s.push_back(n); int ans=0; for(int i=n-1;i>=l;i--){ if(v[i]<=t){ rn=min(rn,v[i]-i); while(s.back()!=n && t-s.back()>=rn){ s.pop_back(); } ans++; } else{ g[s.back()].ch.push_back(i); s.push_back(i); rn=2e9; } } dfs(rt,rt); dfs2(rt,rt,0); sort(z.begin(),z.end(),greater<int>()); d=min(d,(int)z.size()); for(int i=d;i<z.size();i++){ ans+=z[i]; } cout << ans << "\n"; return 0; }

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:80:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i=d;i<z.size();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...