oj.uz

답안 #675889

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
675889 2022-12-28T09:45:40 Z ParsaS The short shank; Redemption (BOI21_prison) C++17
100 / 100
 1177 ms 292004 KB 
// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 2e6 + 5;
int n, D, T, t[N];
int lt[N], par[N], tim, tin[N], tout[N];
vector<int> adj[N];
vector<pair<int, int> > vec;
bool vis[N];
int seg[N << 2], mx[N << 2], lz[N << 2], h[N];

void dfs(int v) {
    tin[v] = tim++;
    vec.pb(mp(h[v], v));
    for (auto u : adj[v]) {
        h[u] = h[v] + 1;
        dfs(u);
    }
    tout[v] = tim - 1;
}
void build(int v = 1, int tl = 0, int tr = tim) {
    if (tl == tr) {
        seg[v] = vec[tl].se; 
        mx[v] = vec[tl].fi;
        return;
    }
    int mid = (tl + tr) >> 1;
    build(v << 1, tl, mid);
    build(v << 1 | 1, mid + 1, tr);
    seg[v] = seg[v << 1];
    mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
    if (h[seg[v << 1 | 1]] > h[seg[v << 1]])
        seg[v] = seg[v << 1 | 1];
}
void shift(int v, int tl, int tr) {
    mx[v] -= lz[v];
    if (tl < tr) {
        lz[v << 1] += lz[v];
        lz[v << 1 | 1] += lz[v];
    }
    lz[v] = 0;
}
void upd(int l, int r, int v = 1, int tl = 0, int tr = tim) {
    shift(v, tl, tr);
    if (l > tr || r < tl)
        return;
    if (tl >= l && tr <= r) {
        lz[v]++;
        shift(v, tl, tr);
        return;
    }
    int mid = (tl + tr) >> 1;
    upd(l, r, v << 1, tl, mid);
    upd(l, r, v << 1 | 1, mid + 1, tr);
    seg[v] = seg[v << 1];
    mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
    if (mx[v] == mx[v << 1 | 1])
        seg[v] = seg[v << 1 | 1];
}

void solve() {
    cin >> n >> D >> T;
    for (int i = 0; i < n; i++)
        cin >> t[i];
    stack<int> st;
    memset(par, -1, sizeof par);
    memset(lt, -1, sizeof lt);
    vector<int> tmp;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && t[st.top()] + i - st.top() > T) {
            tmp.pb(st.top());
            st.pop();
        }
        if (t[i] > T && st.empty())
            cnt++;
        if (!st.empty() && t[i] > T) {
            lt[i] = st.top();
            while (!tmp.empty() && tmp.back() >= lt[i]) {
                int j = tmp.back();
                if (lt[j] != -1) {
                    adj[i].pb(j);
                    par[j] = i;
                }
                tmp.pop_back();
            }
        }
        st.push(i);
    }
    for (int i = 0; i < n; i++) {
        if (par[i] == -1 && lt[i] != -1) {
            adj[n].pb(i);
            par[i] = n;
        }
    }
    dfs(n);
    tim--;
    build();
    vis[n] = true;
    int ans = 0;
    while (D--) {
        shift(1, 0, n);
        int v = seg[1];
        if (mx[1] <= 0)
            break;
        ans += mx[1];
        while (!vis[v]) {
            upd(tin[v], tout[v]);
            vis[v] = true;
            v = par[v];
        }
    }
    cout << n - ans - cnt << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 62924 KB Output is correct
2 Correct 29 ms 62932 KB Output is correct
3 Correct 28 ms 62932 KB Output is correct
4 Correct 31 ms 62932 KB Output is correct
5 Correct 28 ms 62984 KB Output is correct
6 Correct 28 ms 63016 KB Output is correct
7 Correct 28 ms 62932 KB Output is correct
8 Correct 28 ms 63008 KB Output is correct
9 Correct 28 ms 63036 KB Output is correct
10 Correct 28 ms 62996 KB Output is correct
11 Correct 28 ms 63000 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 62884 KB Output is correct
2 Correct 100 ms 82972 KB Output is correct
3 Correct 91 ms 80436 KB Output is correct
4 Correct 107 ms 90180 KB Output is correct
5 Correct 95 ms 90572 KB Output is correct
6 Correct 128 ms 86352 KB Output is correct
7 Correct 299 ms 134492 KB Output is correct
8 Correct 121 ms 88696 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 62924 KB Output is correct
2 Correct 29 ms 62932 KB Output is correct
3 Correct 28 ms 62932 KB Output is correct
4 Correct 31 ms 62932 KB Output is correct
5 Correct 28 ms 62984 KB Output is correct
6 Correct 28 ms 63016 KB Output is correct
7 Correct 28 ms 62932 KB Output is correct
8 Correct 28 ms 63008 KB Output is correct
9 Correct 28 ms 63036 KB Output is correct
10 Correct 28 ms 62996 KB Output is correct
11 Correct 28 ms 63000 KB Output is correct
12 Correct 31 ms 62924 KB Output is correct
13 Correct 33 ms 63024 KB Output is correct
14 Correct 31 ms 62944 KB Output is correct
15 Correct 29 ms 62920 KB Output is correct
16 Correct 28 ms 62956 KB Output is correct
17 Correct 29 ms 62924 KB Output is correct
18 Correct 34 ms 62944 KB Output is correct
19 Correct 33 ms 62932 KB Output is correct
20 Correct 29 ms 62932 KB Output is correct
21 Correct 29 ms 62924 KB Output is correct
22 Correct 31 ms 62968 KB Output is correct
23 Correct 29 ms 63192 KB Output is correct
24 Correct 30 ms 63148 KB Output is correct
25 Correct 30 ms 63252 KB Output is correct
26 Correct 30 ms 63140 KB Output is correct
27 Correct 30 ms 63192 KB Output is correct
28 Correct 32 ms 63132 KB Output is correct
29 Correct 31 ms 63152 KB Output is correct
30 Correct 30 ms 63188 KB Output is correct
31 Correct 30 ms 63192 KB Output is correct
32 Correct 31 ms 63224 KB Output is correct
33 Correct 30 ms 63188 KB Output is correct
34 Correct 31 ms 63292 KB Output is correct
35 Correct 42 ms 63280 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 62952 KB Output is correct
2 Correct 46 ms 67048 KB Output is correct
3 Correct 40 ms 66756 KB Output is correct
4 Correct 55 ms 69768 KB Output is correct
5 Correct 55 ms 70816 KB Output is correct
6 Correct 56 ms 70860 KB Output is correct
7 Correct 41 ms 66440 KB Output is correct
8 Correct 40 ms 66068 KB Output is correct
9 Correct 59 ms 74972 KB Output is correct
10 Correct 36 ms 66468 KB Output is correct

Subtask #5
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 62924 KB Output is correct
2 Correct 29 ms 62932 KB Output is correct
3 Correct 28 ms 62932 KB Output is correct
4 Correct 31 ms 62932 KB Output is correct
5 Correct 28 ms 62984 KB Output is correct
6 Correct 28 ms 63016 KB Output is correct
7 Correct 28 ms 62932 KB Output is correct
8 Correct 28 ms 63008 KB Output is correct
9 Correct 28 ms 63036 KB Output is correct
10 Correct 28 ms 62996 KB Output is correct
11 Correct 28 ms 63000 KB Output is correct
12 Correct 31 ms 62924 KB Output is correct
13 Correct 33 ms 63024 KB Output is correct
14 Correct 31 ms 62944 KB Output is correct
15 Correct 29 ms 62920 KB Output is correct
16 Correct 28 ms 62956 KB Output is correct
17 Correct 29 ms 62924 KB Output is correct
18 Correct 34 ms 62944 KB Output is correct
19 Correct 33 ms 62932 KB Output is correct
20 Correct 29 ms 62932 KB Output is correct
21 Correct 29 ms 62924 KB Output is correct
22 Correct 31 ms 62968 KB Output is correct
23 Correct 29 ms 63192 KB Output is correct
24 Correct 30 ms 63148 KB Output is correct
25 Correct 30 ms 63252 KB Output is correct
26 Correct 30 ms 63140 KB Output is correct
27 Correct 30 ms 63192 KB Output is correct
28 Correct 32 ms 63132 KB Output is correct
29 Correct 31 ms 63152 KB Output is correct
30 Correct 30 ms 63188 KB Output is correct
31 Correct 30 ms 63192 KB Output is correct
32 Correct 31 ms 63224 KB Output is correct
33 Correct 30 ms 63188 KB Output is correct
34 Correct 31 ms 63292 KB Output is correct
35 Correct 42 ms 63280 KB Output is correct
36 Correct 33 ms 62952 KB Output is correct
37 Correct 46 ms 67048 KB Output is correct
38 Correct 40 ms 66756 KB Output is correct
39 Correct 55 ms 69768 KB Output is correct
40 Correct 55 ms 70816 KB Output is correct
41 Correct 56 ms 70860 KB Output is correct
42 Correct 41 ms 66440 KB Output is correct
43 Correct 40 ms 66068 KB Output is correct
44 Correct 59 ms 74972 KB Output is correct
45 Correct 36 ms 66468 KB Output is correct
46 Correct 27 ms 62928 KB Output is correct
47 Correct 28 ms 62976 KB Output is correct
48 Correct 28 ms 62932 KB Output is correct
49 Correct 28 ms 63008 KB Output is correct
50 Correct 30 ms 62960 KB Output is correct
51 Correct 28 ms 63024 KB Output is correct
52 Correct 31 ms 62952 KB Output is correct
53 Correct 29 ms 62920 KB Output is correct
54 Correct 29 ms 62932 KB Output is correct
55 Correct 34 ms 62984 KB Output is correct
56 Correct 29 ms 62964 KB Output is correct
57 Correct 34 ms 63188 KB Output is correct
58 Correct 30 ms 63104 KB Output is correct
59 Correct 30 ms 63180 KB Output is correct
60 Correct 31 ms 63184 KB Output is correct
61 Correct 31 ms 63176 KB Output is correct
62 Correct 30 ms 63128 KB Output is correct
63 Correct 35 ms 63188 KB Output is correct
64 Correct 29 ms 63096 KB Output is correct
65 Correct 30 ms 63188 KB Output is correct
66 Correct 30 ms 63104 KB Output is correct
67 Correct 30 ms 63188 KB Output is correct
68 Correct 31 ms 63292 KB Output is correct
69 Correct 32 ms 63316 KB Output is correct
70 Correct 30 ms 62980 KB Output is correct
71 Correct 41 ms 67000 KB Output is correct
72 Correct 40 ms 66664 KB Output is correct
73 Correct 63 ms 69664 KB Output is correct
74 Correct 58 ms 70692 KB Output is correct
75 Correct 55 ms 70964 KB Output is correct
76 Correct 43 ms 66440 KB Output is correct
77 Correct 50 ms 66080 KB Output is correct
78 Correct 61 ms 75056 KB Output is correct
79 Correct 36 ms 66480 KB Output is correct
80 Correct 44 ms 67100 KB Output is correct
81 Correct 50 ms 67428 KB Output is correct
82 Correct 55 ms 67048 KB Output is correct
83 Correct 61 ms 68548 KB Output is correct
84 Correct 56 ms 67396 KB Output is correct
85 Correct 74 ms 71260 KB Output is correct
86 Correct 63 ms 68208 KB Output is correct
87 Correct 46 ms 66004 KB Output is correct
88 Correct 80 ms 72156 KB Output is correct
89 Correct 58 ms 74692 KB Output is correct
90 Correct 60 ms 71072 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 62924 KB Output is correct
2 Correct 29 ms 62932 KB Output is correct
3 Correct 28 ms 62932 KB Output is correct
4 Correct 31 ms 62932 KB Output is correct
5 Correct 28 ms 62984 KB Output is correct
6 Correct 28 ms 63016 KB Output is correct
7 Correct 28 ms 62932 KB Output is correct
8 Correct 28 ms 63008 KB Output is correct
9 Correct 28 ms 63036 KB Output is correct
10 Correct 28 ms 62996 KB Output is correct
11 Correct 28 ms 63000 KB Output is correct
12 Correct 28 ms 62884 KB Output is correct
13 Correct 100 ms 82972 KB Output is correct
14 Correct 91 ms 80436 KB Output is correct
15 Correct 107 ms 90180 KB Output is correct
16 Correct 95 ms 90572 KB Output is correct
17 Correct 128 ms 86352 KB Output is correct
18 Correct 299 ms 134492 KB Output is correct
19 Correct 121 ms 88696 KB Output is correct
20 Correct 31 ms 62924 KB Output is correct
21 Correct 33 ms 63024 KB Output is correct
22 Correct 31 ms 62944 KB Output is correct
23 Correct 29 ms 62920 KB Output is correct
24 Correct 28 ms 62956 KB Output is correct
25 Correct 29 ms 62924 KB Output is correct
26 Correct 34 ms 62944 KB Output is correct
27 Correct 33 ms 62932 KB Output is correct
28 Correct 29 ms 62932 KB Output is correct
29 Correct 29 ms 62924 KB Output is correct
30 Correct 31 ms 62968 KB Output is correct
31 Correct 29 ms 63192 KB Output is correct
32 Correct 30 ms 63148 KB Output is correct
33 Correct 30 ms 63252 KB Output is correct
34 Correct 30 ms 63140 KB Output is correct
35 Correct 30 ms 63192 KB Output is correct
36 Correct 32 ms 63132 KB Output is correct
37 Correct 31 ms 63152 KB Output is correct
38 Correct 30 ms 63188 KB Output is correct
39 Correct 30 ms 63192 KB Output is correct
40 Correct 31 ms 63224 KB Output is correct
41 Correct 30 ms 63188 KB Output is correct
42 Correct 31 ms 63292 KB Output is correct
43 Correct 42 ms 63280 KB Output is correct
44 Correct 33 ms 62952 KB Output is correct
45 Correct 46 ms 67048 KB Output is correct
46 Correct 40 ms 66756 KB Output is correct
47 Correct 55 ms 69768 KB Output is correct
48 Correct 55 ms 70816 KB Output is correct
49 Correct 56 ms 70860 KB Output is correct
50 Correct 41 ms 66440 KB Output is correct
51 Correct 40 ms 66068 KB Output is correct
52 Correct 59 ms 74972 KB Output is correct
53 Correct 36 ms 66468 KB Output is correct
54 Correct 27 ms 62928 KB Output is correct
55 Correct 28 ms 62976 KB Output is correct
56 Correct 28 ms 62932 KB Output is correct
57 Correct 28 ms 63008 KB Output is correct
58 Correct 30 ms 62960 KB Output is correct
59 Correct 28 ms 63024 KB Output is correct
60 Correct 31 ms 62952 KB Output is correct
61 Correct 29 ms 62920 KB Output is correct
62 Correct 29 ms 62932 KB Output is correct
63 Correct 34 ms 62984 KB Output is correct
64 Correct 29 ms 62964 KB Output is correct
65 Correct 34 ms 63188 KB Output is correct
66 Correct 30 ms 63104 KB Output is correct
67 Correct 30 ms 63180 KB Output is correct
68 Correct 31 ms 63184 KB Output is correct
69 Correct 31 ms 63176 KB Output is correct
70 Correct 30 ms 63128 KB Output is correct
71 Correct 35 ms 63188 KB Output is correct
72 Correct 29 ms 63096 KB Output is correct
73 Correct 30 ms 63188 KB Output is correct
74 Correct 30 ms 63104 KB Output is correct
75 Correct 30 ms 63188 KB Output is correct
76 Correct 31 ms 63292 KB Output is correct
77 Correct 32 ms 63316 KB Output is correct
78 Correct 30 ms 62980 KB Output is correct
79 Correct 41 ms 67000 KB Output is correct
80 Correct 40 ms 66664 KB Output is correct
81 Correct 63 ms 69664 KB Output is correct
82 Correct 58 ms 70692 KB Output is correct
83 Correct 55 ms 70964 KB Output is correct
84 Correct 43 ms 66440 KB Output is correct
85 Correct 50 ms 66080 KB Output is correct
86 Correct 61 ms 75056 KB Output is correct
87 Correct 36 ms 66480 KB Output is correct
88 Correct 44 ms 67100 KB Output is correct
89 Correct 50 ms 67428 KB Output is correct
90 Correct 55 ms 67048 KB Output is correct
91 Correct 61 ms 68548 KB Output is correct
92 Correct 56 ms 67396 KB Output is correct
93 Correct 74 ms 71260 KB Output is correct
94 Correct 63 ms 68208 KB Output is correct
95 Correct 46 ms 66004 KB Output is correct
96 Correct 80 ms 72156 KB Output is correct
97 Correct 58 ms 74692 KB Output is correct
98 Correct 60 ms 71072 KB Output is correct
99 Correct 28 ms 62932 KB Output is correct
100 Correct 31 ms 62988 KB Output is correct
101 Correct 29 ms 62968 KB Output is correct
102 Correct 30 ms 63028 KB Output is correct
103 Correct 29 ms 62904 KB Output is correct
104 Correct 29 ms 62924 KB Output is correct
105 Correct 29 ms 63044 KB Output is correct
106 Correct 28 ms 63000 KB Output is correct
107 Correct 28 ms 62932 KB Output is correct
108 Correct 30 ms 62912 KB Output is correct
109 Correct 29 ms 63020 KB Output is correct
110 Correct 34 ms 62996 KB Output is correct
111 Correct 99 ms 82876 KB Output is correct
112 Correct 92 ms 80392 KB Output is correct
113 Correct 107 ms 90196 KB Output is correct
114 Correct 100 ms 90560 KB Output is correct
115 Correct 133 ms 86452 KB Output is correct
116 Correct 254 ms 134412 KB Output is correct
117 Correct 117 ms 88720 KB Output is correct
118 Correct 30 ms 63268 KB Output is correct
119 Correct 31 ms 63188 KB Output is correct
120 Correct 31 ms 63212 KB Output is correct
121 Correct 37 ms 63128 KB Output is correct
122 Correct 30 ms 63308 KB Output is correct
123 Correct 33 ms 63188 KB Output is correct
124 Correct 30 ms 63188 KB Output is correct
125 Correct 30 ms 63188 KB Output is correct
126 Correct 31 ms 63152 KB Output is correct
127 Correct 29 ms 63188 KB Output is correct
128 Correct 29 ms 63188 KB Output is correct
129 Correct 35 ms 63212 KB Output is correct
130 Correct 35 ms 63264 KB Output is correct
131 Correct 33 ms 62956 KB Output is correct
132 Correct 47 ms 67100 KB Output is correct
133 Correct 43 ms 66640 KB Output is correct
134 Correct 54 ms 69700 KB Output is correct
135 Correct 53 ms 70728 KB Output is correct
136 Correct 57 ms 70896 KB Output is correct
137 Correct 41 ms 66440 KB Output is correct
138 Correct 50 ms 66052 KB Output is correct
139 Correct 64 ms 75072 KB Output is correct
140 Correct 37 ms 66520 KB Output is correct
141 Correct 44 ms 67004 KB Output is correct
142 Correct 50 ms 67380 KB Output is correct
143 Correct 47 ms 67056 KB Output is correct
144 Correct 56 ms 68548 KB Output is correct
145 Correct 60 ms 67416 KB Output is correct
146 Correct 62 ms 71156 KB Output is correct
147 Correct 52 ms 68200 KB Output is correct
148 Correct 44 ms 65976 KB Output is correct
149 Correct 65 ms 72168 KB Output is correct
150 Correct 59 ms 74624 KB Output is correct
151 Correct 62 ms 70968 KB Output is correct
152 Correct 336 ms 151764 KB Output is correct
153 Correct 364 ms 174556 KB Output is correct
154 Correct 367 ms 148812 KB Output is correct
155 Correct 684 ms 210408 KB Output is correct
156 Correct 657 ms 191460 KB Output is correct
157 Correct 325 ms 141744 KB Output is correct
158 Correct 473 ms 174776 KB Output is correct
159 Correct 1177 ms 292004 KB Output is correct
160 Correct 1124 ms 272464 KB Output is correct
161 Correct 422 ms 141676 KB Output is correct
162 Correct 383 ms 143744 KB Output is correct