제출 #863225

#제출 시각아이디문제언어결과실행 시간메모리
863225arashMLGThe short shank; Redemption (BOI21_prison)C++17
100 / 100
1172 ms430224 KiB
#include<bits/stdc++.h> #ifdef LOCAL #include "Essentials/algo/debug.h" #else #define debug(...) 69 #endif using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N = 2e6+ 23; const int inf = 1e9+7; #define F first #define S second #define pb push_back #define kill(x) cout<<x<<endl, exit(0); #define all(x) x.begin(),x.end() #define sz(x) (int)x.size() #define lc (v << 1) #define rc ((v<<1) |1) //#define int ll #pragma GCC optimize("O3,unroll-loops") int n,d,T; int a[N]; int l[N]; stack<int> st; void calcl() { for(int i = 1; i<= n; i ++) { if(a[i] <= T) { st.push(i); l[i] = i; debug(i,l[i]); continue; } while(sz(st) && (i-st.top() + a[st.top()]) > T) st.pop(); if(st.empty()) l[i] = 0; else l[i] = st.top(); st.push(i); debug(i,l[i]); } } struct Seg { pii t[N<<2]; int lz[N<<2]; void build(int v=1,int tl = 0 ,int tr = N){ if(tr- tl == 1) { t[v] = {0,tl}; return; } int mid=(tl+tr)/2; build(lc,tl,mid); build(rc,mid,tr); t[v] = max(t[lc],t[rc]); } void shift(int v) { if(lz[v] == 0) return; t[lc].F += lz[v]; t[rc].F += lz[v]; lz[lc] += lz[v]; lz[rc] += lz[v]; lz[v] = 0; } void upd(int l,int r,int x,int v=1,int tl =0 ,int tr =N) { if(l > r) return; if(l == tl && r == tr-1) { t[v].F += x; lz[v] += x; return; } shift(v); int mid=(tl+tr)/2; upd(l,min(mid-1,r),x,lc,tl,mid); upd(max(l,mid),r,x,rc,mid,tr); t[v] = max(t[lc],t[rc]); } /*pii gmx(int l,int r,int v=1,int tl=0,int tr = N) { if(l > r) return 0; if(l == tl && r == tr-1) return t[v]; shift(v); int mid=(tl +tr)/2; return max( gmx }*/ } s; vector<int> G[N],GP[N]; int ans; void buildg() { while(sz(st)) st.pop(); st.push(0); for(int i = n;i >= 1 ; i--) { if(l[i] ==i) { continue; } if(l[i] == 0){ ans --; continue; } while(st.top() && l[st.top()] > i) st.pop(); debug(st.top(),i); G[st.top()].pb(i); st.push(i); } } bool mark[N]; int St[N],ft[N]; int h[N]; int timer; int par[N]; void dfs1(int v) { St[v] = timer ++; for(int u : G[v]) { dfs1(u); GP[St[v]].pb(St[u]); } } void dfs2(int v) { ft[v] = v; for(int u : GP[v]) { h[u] = h[v] +1; par[u] = v; dfs2(u); ft[v] = ft[u]; } s.upd(v,ft[v],1); } int32_t main() { cin.tie(nullptr)->sync_with_stdio(false); cin>>n>>d>>T; for(int i = 1; i<= n ; i++) cin>>a[i]; calcl(); ans =n; buildg(); s.build(); dfs1(0); h[0] =1; dfs2(0); while(s.t[1].F != 0 && d>0) { int x = s.t[1].S; if(sz(GP[x]) != 0) break; d--; while(!mark[x]) { mark[x] = true; if(x !=0) ans--; s.upd(x,ft[x],-1); x = par[x]; } } cout<<ans<<'\n'; return 0; }

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

prison.cpp: In function 'void calcl()':
prison.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
prison.cpp:37:4: note: in expansion of macro 'debug'
   37 |    debug(i,l[i]);
      |    ^~~~~
prison.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
prison.cpp:44:3: note: in expansion of macro 'debug'
   44 |   debug(i,l[i]);
      |   ^~~~~
prison.cpp: In function 'void buildg()':
prison.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
prison.cpp:114:3: note: in expansion of macro 'debug'
  114 |   debug(st.top(),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...