oj.uz

답안 #666186

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
666186 2022-11-27T17:11:15 Z urosk The short shank; Redemption (BOI21_prison) C++14
100 / 100
 519 ms 299452 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
using namespace __gnu_pbds;
#define maxn 2000005
ll n,d,t,ans;
ll a[maxn],p[maxn],b[maxn];
vector<ll> g[maxn];
bool vis[maxn],bio[maxn];
ll dub[maxn],maxi[maxn];
ll dfs(ll u){
    ll x = u;
    vis[u] = 1;
    for(ll s : g[u]){
        if(vis[s]) continue;
        dub[s] = dub[u] + 1;
        ll y = dfs(s);
        if(dub[y]>dub[x]) x = y;
    }
    return maxi[u] = x;
}
bool cmp(ll x,ll y){
    return dub[x]>dub[y];
}
ll c[maxn];
void tc(){
    cin >> n >> d >> t;
    for(ll i = 1;i<=n;i++) cin >> a[i];
    stack<ll> s;
    ll rmax = 0,r = 0;
    for(ll i = 1;i<=n;i++){
        if(a[i]>t&&r>=i){
            b[i] = rmax;
            rmax = 0;
            while(sz(s)&&b[i]<i){
                p[s.top()] = i;
                b[i] = max(b[i],b[s.top()]);
                s.pop();
            }
            s.push(i);
        }else rmax = max(rmax,i+t-a[i]);
        c[i] = r;
        r = max(r,rmax);
    }
    while(sz(s)){
        if(c[s.top()]>=s.top()) p[s.top()] = s.top();
        s.pop();
    }
    for(ll i = 1;i<=n;i++) if(a[i]>t) g[p[i]].pb(i);
    priority_queue<pll> pq;
    ans = n;
    for(ll i = n;i>=1;i--){
        if(a[i]<=t) continue;
        if(vis[i]) continue;
        if(sz(g[i])==0&&c[i]<i){ans--;continue;}
        dub[i] = 1;
        ll x = dfs(i);
        pq.push({dub[x],x});
    }
    while(sz(pq)&&d){
        ll u = pq.top().sc;
        ll dept = pq.top().fi;
        ans-=dept;
        pq.pop();
        while(1){
            bio[u] = 1;
            for(ll s : g[u]){
                if(!bio[s]) pq.push({dub[maxi[s]]-dub[u],maxi[s]});
            }
            if(bio[p[u]]) break;
            u = p[u];
        }
        d--;
    }
    cout<<ans<<endl;
}
int main(){
	daj_mi_malo_vremena
    int t; t = 1;
    while(t--){
        tc();
    }
	return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 25 ms 47384 KB Output is correct
3 Correct 23 ms 47280 KB Output is correct
4 Correct 22 ms 47320 KB Output is correct
5 Correct 23 ms 47384 KB Output is correct
6 Correct 24 ms 47316 KB Output is correct
7 Correct 25 ms 47316 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 23 ms 47360 KB Output is correct
10 Correct 22 ms 47356 KB Output is correct
11 Correct 26 ms 47256 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 47336 KB Output is correct
2 Correct 99 ms 79212 KB Output is correct
3 Correct 96 ms 77260 KB Output is correct
4 Correct 94 ms 81484 KB Output is correct
5 Correct 97 ms 80584 KB Output is correct
6 Correct 105 ms 83644 KB Output is correct
7 Correct 118 ms 122460 KB Output is correct
8 Correct 100 ms 86920 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 25 ms 47384 KB Output is correct
3 Correct 23 ms 47280 KB Output is correct
4 Correct 22 ms 47320 KB Output is correct
5 Correct 23 ms 47384 KB Output is correct
6 Correct 24 ms 47316 KB Output is correct
7 Correct 25 ms 47316 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 23 ms 47360 KB Output is correct
10 Correct 22 ms 47356 KB Output is correct
11 Correct 26 ms 47256 KB Output is correct
12 Correct 23 ms 47348 KB Output is correct
13 Correct 24 ms 47440 KB Output is correct
14 Correct 26 ms 47320 KB Output is correct
15 Correct 23 ms 47316 KB Output is correct
16 Correct 23 ms 47292 KB Output is correct
17 Correct 24 ms 47384 KB Output is correct
18 Correct 22 ms 47376 KB Output is correct
19 Correct 22 ms 47304 KB Output is correct
20 Correct 23 ms 47352 KB Output is correct
21 Correct 23 ms 47308 KB Output is correct
22 Correct 23 ms 47324 KB Output is correct
23 Correct 24 ms 47572 KB Output is correct
24 Correct 27 ms 47608 KB Output is correct
25 Correct 25 ms 47568 KB Output is correct
26 Correct 27 ms 47572 KB Output is correct
27 Correct 26 ms 47628 KB Output is correct
28 Correct 24 ms 47576 KB Output is correct
29 Correct 24 ms 47608 KB Output is correct
30 Correct 23 ms 47568 KB Output is correct
31 Correct 24 ms 47572 KB Output is correct
32 Correct 24 ms 47568 KB Output is correct
33 Correct 23 ms 47604 KB Output is correct
34 Correct 24 ms 47632 KB Output is correct
35 Correct 28 ms 47564 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 47372 KB Output is correct
2 Correct 35 ms 52560 KB Output is correct
3 Correct 35 ms 52224 KB Output is correct
4 Correct 34 ms 54604 KB Output is correct
5 Correct 35 ms 55044 KB Output is correct
6 Correct 35 ms 55300 KB Output is correct
7 Correct 33 ms 52324 KB Output is correct
8 Correct 33 ms 52260 KB Output is correct
9 Correct 37 ms 58444 KB Output is correct
10 Correct 32 ms 53708 KB Output is correct

Subtask #5
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 25 ms 47384 KB Output is correct
3 Correct 23 ms 47280 KB Output is correct
4 Correct 22 ms 47320 KB Output is correct
5 Correct 23 ms 47384 KB Output is correct
6 Correct 24 ms 47316 KB Output is correct
7 Correct 25 ms 47316 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 23 ms 47360 KB Output is correct
10 Correct 22 ms 47356 KB Output is correct
11 Correct 26 ms 47256 KB Output is correct
12 Correct 23 ms 47348 KB Output is correct
13 Correct 24 ms 47440 KB Output is correct
14 Correct 26 ms 47320 KB Output is correct
15 Correct 23 ms 47316 KB Output is correct
16 Correct 23 ms 47292 KB Output is correct
17 Correct 24 ms 47384 KB Output is correct
18 Correct 22 ms 47376 KB Output is correct
19 Correct 22 ms 47304 KB Output is correct
20 Correct 23 ms 47352 KB Output is correct
21 Correct 23 ms 47308 KB Output is correct
22 Correct 23 ms 47324 KB Output is correct
23 Correct 24 ms 47572 KB Output is correct
24 Correct 27 ms 47608 KB Output is correct
25 Correct 25 ms 47568 KB Output is correct
26 Correct 27 ms 47572 KB Output is correct
27 Correct 26 ms 47628 KB Output is correct
28 Correct 24 ms 47576 KB Output is correct
29 Correct 24 ms 47608 KB Output is correct
30 Correct 23 ms 47568 KB Output is correct
31 Correct 24 ms 47572 KB Output is correct
32 Correct 24 ms 47568 KB Output is correct
33 Correct 23 ms 47604 KB Output is correct
34 Correct 24 ms 47632 KB Output is correct
35 Correct 28 ms 47564 KB Output is correct
36 Correct 24 ms 47372 KB Output is correct
37 Correct 35 ms 52560 KB Output is correct
38 Correct 35 ms 52224 KB Output is correct
39 Correct 34 ms 54604 KB Output is correct
40 Correct 35 ms 55044 KB Output is correct
41 Correct 35 ms 55300 KB Output is correct
42 Correct 33 ms 52324 KB Output is correct
43 Correct 33 ms 52260 KB Output is correct
44 Correct 37 ms 58444 KB Output is correct
45 Correct 32 ms 53708 KB Output is correct
46 Correct 23 ms 47316 KB Output is correct
47 Correct 23 ms 47316 KB Output is correct
48 Correct 22 ms 47392 KB Output is correct
49 Correct 23 ms 47316 KB Output is correct
50 Correct 23 ms 47316 KB Output is correct
51 Correct 22 ms 47264 KB Output is correct
52 Correct 23 ms 47316 KB Output is correct
53 Correct 23 ms 47280 KB Output is correct
54 Correct 24 ms 47292 KB Output is correct
55 Correct 23 ms 47316 KB Output is correct
56 Correct 23 ms 47300 KB Output is correct
57 Correct 25 ms 47540 KB Output is correct
58 Correct 23 ms 47608 KB Output is correct
59 Correct 22 ms 47596 KB Output is correct
60 Correct 23 ms 47652 KB Output is correct
61 Correct 22 ms 47652 KB Output is correct
62 Correct 23 ms 47604 KB Output is correct
63 Correct 29 ms 47688 KB Output is correct
64 Correct 28 ms 47644 KB Output is correct
65 Correct 27 ms 47580 KB Output is correct
66 Correct 24 ms 47548 KB Output is correct
67 Correct 23 ms 47652 KB Output is correct
68 Correct 24 ms 47572 KB Output is correct
69 Correct 24 ms 47684 KB Output is correct
70 Correct 24 ms 47240 KB Output is correct
71 Correct 37 ms 53252 KB Output is correct
72 Correct 41 ms 53008 KB Output is correct
73 Correct 36 ms 55188 KB Output is correct
74 Correct 36 ms 55764 KB Output is correct
75 Correct 37 ms 56012 KB Output is correct
76 Correct 41 ms 52796 KB Output is correct
77 Correct 37 ms 52312 KB Output is correct
78 Correct 42 ms 58444 KB Output is correct
79 Correct 42 ms 53696 KB Output is correct
80 Correct 42 ms 53060 KB Output is correct
81 Correct 43 ms 53240 KB Output is correct
82 Correct 37 ms 53076 KB Output is correct
83 Correct 37 ms 54096 KB Output is correct
84 Correct 35 ms 52824 KB Output is correct
85 Correct 38 ms 56396 KB Output is correct
86 Correct 38 ms 53948 KB Output is correct
87 Correct 39 ms 52312 KB Output is correct
88 Correct 35 ms 57408 KB Output is correct
89 Correct 34 ms 58188 KB Output is correct
90 Correct 35 ms 56636 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 25 ms 47384 KB Output is correct
3 Correct 23 ms 47280 KB Output is correct
4 Correct 22 ms 47320 KB Output is correct
5 Correct 23 ms 47384 KB Output is correct
6 Correct 24 ms 47316 KB Output is correct
7 Correct 25 ms 47316 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 23 ms 47360 KB Output is correct
10 Correct 22 ms 47356 KB Output is correct
11 Correct 26 ms 47256 KB Output is correct
12 Correct 25 ms 47336 KB Output is correct
13 Correct 99 ms 79212 KB Output is correct
14 Correct 96 ms 77260 KB Output is correct
15 Correct 94 ms 81484 KB Output is correct
16 Correct 97 ms 80584 KB Output is correct
17 Correct 105 ms 83644 KB Output is correct
18 Correct 118 ms 122460 KB Output is correct
19 Correct 100 ms 86920 KB Output is correct
20 Correct 23 ms 47348 KB Output is correct
21 Correct 24 ms 47440 KB Output is correct
22 Correct 26 ms 47320 KB Output is correct
23 Correct 23 ms 47316 KB Output is correct
24 Correct 23 ms 47292 KB Output is correct
25 Correct 24 ms 47384 KB Output is correct
26 Correct 22 ms 47376 KB Output is correct
27 Correct 22 ms 47304 KB Output is correct
28 Correct 23 ms 47352 KB Output is correct
29 Correct 23 ms 47308 KB Output is correct
30 Correct 23 ms 47324 KB Output is correct
31 Correct 24 ms 47572 KB Output is correct
32 Correct 27 ms 47608 KB Output is correct
33 Correct 25 ms 47568 KB Output is correct
34 Correct 27 ms 47572 KB Output is correct
35 Correct 26 ms 47628 KB Output is correct
36 Correct 24 ms 47576 KB Output is correct
37 Correct 24 ms 47608 KB Output is correct
38 Correct 23 ms 47568 KB Output is correct
39 Correct 24 ms 47572 KB Output is correct
40 Correct 24 ms 47568 KB Output is correct
41 Correct 23 ms 47604 KB Output is correct
42 Correct 24 ms 47632 KB Output is correct
43 Correct 28 ms 47564 KB Output is correct
44 Correct 24 ms 47372 KB Output is correct
45 Correct 35 ms 52560 KB Output is correct
46 Correct 35 ms 52224 KB Output is correct
47 Correct 34 ms 54604 KB Output is correct
48 Correct 35 ms 55044 KB Output is correct
49 Correct 35 ms 55300 KB Output is correct
50 Correct 33 ms 52324 KB Output is correct
51 Correct 33 ms 52260 KB Output is correct
52 Correct 37 ms 58444 KB Output is correct
53 Correct 32 ms 53708 KB Output is correct
54 Correct 23 ms 47316 KB Output is correct
55 Correct 23 ms 47316 KB Output is correct
56 Correct 22 ms 47392 KB Output is correct
57 Correct 23 ms 47316 KB Output is correct
58 Correct 23 ms 47316 KB Output is correct
59 Correct 22 ms 47264 KB Output is correct
60 Correct 23 ms 47316 KB Output is correct
61 Correct 23 ms 47280 KB Output is correct
62 Correct 24 ms 47292 KB Output is correct
63 Correct 23 ms 47316 KB Output is correct
64 Correct 23 ms 47300 KB Output is correct
65 Correct 25 ms 47540 KB Output is correct
66 Correct 23 ms 47608 KB Output is correct
67 Correct 22 ms 47596 KB Output is correct
68 Correct 23 ms 47652 KB Output is correct
69 Correct 22 ms 47652 KB Output is correct
70 Correct 23 ms 47604 KB Output is correct
71 Correct 29 ms 47688 KB Output is correct
72 Correct 28 ms 47644 KB Output is correct
73 Correct 27 ms 47580 KB Output is correct
74 Correct 24 ms 47548 KB Output is correct
75 Correct 23 ms 47652 KB Output is correct
76 Correct 24 ms 47572 KB Output is correct
77 Correct 24 ms 47684 KB Output is correct
78 Correct 24 ms 47240 KB Output is correct
79 Correct 37 ms 53252 KB Output is correct
80 Correct 41 ms 53008 KB Output is correct
81 Correct 36 ms 55188 KB Output is correct
82 Correct 36 ms 55764 KB Output is correct
83 Correct 37 ms 56012 KB Output is correct
84 Correct 41 ms 52796 KB Output is correct
85 Correct 37 ms 52312 KB Output is correct
86 Correct 42 ms 58444 KB Output is correct
87 Correct 42 ms 53696 KB Output is correct
88 Correct 42 ms 53060 KB Output is correct
89 Correct 43 ms 53240 KB Output is correct
90 Correct 37 ms 53076 KB Output is correct
91 Correct 37 ms 54096 KB Output is correct
92 Correct 35 ms 52824 KB Output is correct
93 Correct 38 ms 56396 KB Output is correct
94 Correct 38 ms 53948 KB Output is correct
95 Correct 39 ms 52312 KB Output is correct
96 Correct 35 ms 57408 KB Output is correct
97 Correct 34 ms 58188 KB Output is correct
98 Correct 35 ms 56636 KB Output is correct
99 Correct 23 ms 47316 KB Output is correct
100 Correct 22 ms 47328 KB Output is correct
101 Correct 23 ms 47316 KB Output is correct
102 Correct 23 ms 47272 KB Output is correct
103 Correct 26 ms 47292 KB Output is correct
104 Correct 22 ms 47316 KB Output is correct
105 Correct 23 ms 47348 KB Output is correct
106 Correct 21 ms 47372 KB Output is correct
107 Correct 22 ms 47308 KB Output is correct
108 Correct 24 ms 47312 KB Output is correct
109 Correct 22 ms 47300 KB Output is correct
110 Correct 24 ms 47316 KB Output is correct
111 Correct 107 ms 84116 KB Output is correct
112 Correct 108 ms 82100 KB Output is correct
113 Correct 100 ms 84860 KB Output is correct
114 Correct 91 ms 82424 KB Output is correct
115 Correct 94 ms 83716 KB Output is correct
116 Correct 137 ms 122528 KB Output is correct
117 Correct 102 ms 86964 KB Output is correct
118 Correct 25 ms 47668 KB Output is correct
119 Correct 25 ms 47564 KB Output is correct
120 Correct 25 ms 47660 KB Output is correct
121 Correct 26 ms 47648 KB Output is correct
122 Correct 27 ms 47560 KB Output is correct
123 Correct 30 ms 47652 KB Output is correct
124 Correct 24 ms 47576 KB Output is correct
125 Correct 25 ms 47560 KB Output is correct
126 Correct 26 ms 47700 KB Output is correct
127 Correct 24 ms 47564 KB Output is correct
128 Correct 25 ms 47572 KB Output is correct
129 Correct 25 ms 47636 KB Output is correct
130 Correct 25 ms 47704 KB Output is correct
131 Correct 24 ms 47316 KB Output is correct
132 Correct 39 ms 53284 KB Output is correct
133 Correct 46 ms 52928 KB Output is correct
134 Correct 36 ms 55148 KB Output is correct
135 Correct 42 ms 55880 KB Output is correct
136 Correct 53 ms 56012 KB Output is correct
137 Correct 37 ms 52852 KB Output is correct
138 Correct 32 ms 52332 KB Output is correct
139 Correct 39 ms 58444 KB Output is correct
140 Correct 34 ms 53792 KB Output is correct
141 Correct 44 ms 53008 KB Output is correct
142 Correct 36 ms 53320 KB Output is correct
143 Correct 38 ms 53072 KB Output is correct
144 Correct 37 ms 53988 KB Output is correct
145 Correct 37 ms 52796 KB Output is correct
146 Correct 46 ms 56452 KB Output is correct
147 Correct 40 ms 53880 KB Output is correct
148 Correct 53 ms 52328 KB Output is correct
149 Correct 36 ms 57392 KB Output is correct
150 Correct 38 ms 58188 KB Output is correct
151 Correct 51 ms 56652 KB Output is correct
152 Correct 385 ms 179396 KB Output is correct
153 Correct 390 ms 181492 KB Output is correct
154 Correct 423 ms 177532 KB Output is correct
155 Correct 418 ms 224660 KB Output is correct
156 Correct 385 ms 195128 KB Output is correct
157 Correct 385 ms 174684 KB Output is correct
158 Correct 414 ms 204760 KB Output is correct
159 Correct 461 ms 299452 KB Output is correct
160 Correct 519 ms 286284 KB Output is correct
161 Correct 417 ms 188228 KB Output is correct
162 Correct 359 ms 189616 KB Output is correct