제출 #734064

#제출 시각아이디문제언어결과실행 시간메모리
734064myrcellaThe short shank; Redemption (BOI21_prison)C++17
35 / 100
2081 ms128236 KiB
//by szh #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pii pair<int,int> #define pll pair<long long,long long> #define pb push_back #define debug(x) cerr<<#x<<"="<<x<<endl #define pq priority_queue #define inf 0x3f #define rep(i,a,b) for (int i=a;i<(b);i++) #define MP make_pair #define SZ(x) (int(x.size())) #define ll long long #define mod 1000000007 #define ALL(x) x.begin(),x.end() void inc(int &a,int b) {a=(a+b)%mod;} void dec(int &a,int b) {a=(a-b+mod)%mod;} int lowbit(int x) {return x&(-x);} ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;} const int maxn = 2e6+10; int n,d,T; int t[maxn]; int le[maxn]; int mn[maxn][21]; int lg[maxn]; vector <int> edge[maxn]; int hson[maxn]; set <pii> s; int dep[maxn]; int query(int l,int r) { int tmp = lg[r-l+1]; return min(mn[l][tmp],mn[r-(1<<tmp)+1][tmp]); } int dfs(int u) { int val = 0; for (int v:edge[u]) { int tmp = dfs(v); if (tmp>val) val=tmp,hson[u] = v; } dep[u] = val+1; s.insert({val+1,u}); return val+1; } int main() { // freopen("input.txt","r",stdin); std::ios::sync_with_stdio(false);cin.tie(0); cin>>n>>d>>T; rep(i,0,n) cin>>t[i],mn[i][0] = t[i]-i; lg[1] = 0; rep(i,2,maxn) lg[i] = lg[i/2]+1; for (int i = n-1;i>=0;i--) rep(j,1,21) { if (i+(1<<j)>n) break; mn[i][j] = min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]); } vector <pii> tmp; int ans = n; rep(i,0,n) { if (t[i]<=T) le[i] = maxn; else { int l = 0,r=i; while (l<r) { int mid = l+r>>1; if (mid==i or query(mid,i-1)+i>T) r=mid; else l = mid+1; } le[i] = l; if (le[i]==0) ans--; else { while (!tmp.empty() and tmp.back().fi>=le[i]) edge[i].pb(tmp.back().se),tmp.pop_back(); tmp.pb({le[i],i}); } } } memset(hson,-1,sizeof(hson)); for (int i = n-1;i>=0;i--) if (le[i]!=maxn and le[i]!=0) dfs(i); rep(i,0,d) { if (s.empty()) break; pii cur = (*(--s.end())); ans -= cur.fi; int u = cur.se; while (u!=-1) s.erase(MP(dep[u],u)),u=hson[u]; } cout<<ans; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

prison.cpp: In function 'int main()':
prison.cpp:70:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     int mid = l+r>>1;
      |               ~^~
#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...