oj.uz

Submission #591751

# Submission time Handle Problem Language Result Execution time Memory
591751 2022-07-07T20:17:21 Z Lobo The short shank; Redemption (BOI21_prison) C++17
100 / 100
 1098 ms 417556 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
 
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const int inf1 = (int) 2e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define MAX(a,b) a > b ? a : b
#define MIN(a,b) a < b ? a : b
 
const int maxn = 2e6+10;
 
int n, d, T, r[maxn], trT[4*maxn], lzqtd[4*maxn], pai[maxn], mark[maxn];
pair<int,int> trqtd[4*maxn], trr[4*maxn], deep[maxn];
vector<int> fq[maxn], g[maxn];
 
void buildT(int no, int l, int r) {
    trT[no] = inf1;
    if(l != r) {
        int f1=((no)<<1);
        int f2=((no)<<1)+1;
        int mid = (l+r)>>1;
        buildT(f1,l,mid);
        buildT(f2,mid+1,r);
    }
}
 
void attT(int no, int l, int r, int pos, int val) {
    if(l > pos || r < pos) return;
    if(l == r) {
        trT[no] = val;
        return;
    }
    int f1=((no)<<1);
    int f2=((no)<<1)+1;
    int mid = (l+r)>>1;
    attT(f1,l,mid,pos,val);
    attT(f2,mid+1,r,pos,val);
    trT[no] = min(trT[f1],trT[f2]);
}
 
int findT(int no, int l, int r, int val) {
    if(l == r) return l;
    int f1 = ((no)<<1);
    int f2 = ((no)<<1)+1;
    int mid = (l+r)>>1;
    if(trT[f2] <= val) return findT(f2,mid+1,r,val);
    return findT(f1,l,mid,val);
}

void dfsdeep(int u) {
    deep[u] = mp(1,u);
    for(auto v : g[u]) {
        dfsdeep(v);
        deep[u] = max(deep[u],mp(deep[v].fr+1,deep[v].sc));
    }
}

void solve() {
    cin >> n >> d >> T;
    int ans = 0;
    buildT(1,1,n);
    vector<pair<pair<int,int>,int>> segs;
    for(int i = 1; i <= n; i++) {
        int t; cin >> t;
        attT(1,1,n,i,t-i);
        if(trT[1] > T-i) {
            r[i] = n+1;
        }
        else {
            r[i] = findT(1,1,n,T-i);
            ans++;
        }
        //i aumenta o qtd de r[i] até i-1
        if(r[i] != i && r[i] != n+1) {
            segs.pb(mp(mp(r[i],i),0));
            segs.pb(mp(mp(i,i),1));
        }
        // cout << i << " " << r[i] << endl;
    }

    stack<int> st;
    int cnt = 0;
    sort(all(segs));
    for(auto X : segs) {
        if(X.sc == 0) {
            ++cnt;
            if(st.size()) {
                pai[cnt] = st.top();
                g[st.top()].pb(cnt);
            }
            st.push(cnt);
        }
        else {
            st.pop();
        }
    }

    // for(int i = 1; i <= cnt; i++) {
    //     cout << i << " " << pai[i] << endl;
    // }

    for(int i = 1; i <= cnt; i++) {
        if(pai[i] == 0) dfsdeep(i);
    }
    for(int i = 1; i <= cnt; i++) {
        fq[deep[i].fr].pb(i);
        // cout << i << " " << deep[i].sc << endl;
    }

    for(int i = n; i >= 1; i--) {
        if(d == 0) break;
        for(auto id : fq[i]) {
            if(d == 0) break;
            if(mark[id]) continue;
            d--;
            int v = deep[id].sc;
            while(v != 0 && mark[v] == 0) {
                ans--;
                mark[v] = 1;
                v = pai[v];
            }
        }
    }
    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94156 KB Output is correct
2 Correct 47 ms 94184 KB Output is correct
3 Correct 44 ms 94424 KB Output is correct
4 Correct 44 ms 94224 KB Output is correct
5 Correct 44 ms 94208 KB Output is correct
6 Correct 45 ms 94224 KB Output is correct
7 Correct 51 ms 94264 KB Output is correct
8 Correct 50 ms 94304 KB Output is correct
9 Correct 49 ms 94220 KB Output is correct
10 Correct 44 ms 94320 KB Output is correct
11 Correct 46 ms 94264 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94156 KB Output is correct
2 Correct 199 ms 119316 KB Output is correct
3 Correct 195 ms 113964 KB Output is correct
4 Correct 216 ms 122500 KB Output is correct
5 Correct 217 ms 123412 KB Output is correct
6 Correct 191 ms 122008 KB Output is correct
7 Correct 310 ms 201984 KB Output is correct
8 Correct 226 ms 125140 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94156 KB Output is correct
2 Correct 47 ms 94184 KB Output is correct
3 Correct 44 ms 94424 KB Output is correct
4 Correct 44 ms 94224 KB Output is correct
5 Correct 44 ms 94208 KB Output is correct
6 Correct 45 ms 94224 KB Output is correct
7 Correct 51 ms 94264 KB Output is correct
8 Correct 50 ms 94304 KB Output is correct
9 Correct 49 ms 94220 KB Output is correct
10 Correct 44 ms 94320 KB Output is correct
11 Correct 46 ms 94264 KB Output is correct
12 Correct 45 ms 94188 KB Output is correct
13 Correct 46 ms 94184 KB Output is correct
14 Correct 45 ms 94280 KB Output is correct
15 Correct 46 ms 94280 KB Output is correct
16 Correct 45 ms 94284 KB Output is correct
17 Correct 46 ms 94260 KB Output is correct
18 Correct 44 ms 94288 KB Output is correct
19 Correct 44 ms 94284 KB Output is correct
20 Correct 46 ms 94312 KB Output is correct
21 Correct 45 ms 94220 KB Output is correct
22 Correct 45 ms 94264 KB Output is correct
23 Correct 45 ms 94560 KB Output is correct
24 Correct 47 ms 94444 KB Output is correct
25 Correct 45 ms 94536 KB Output is correct
26 Correct 52 ms 94468 KB Output is correct
27 Correct 47 ms 94500 KB Output is correct
28 Correct 45 ms 94428 KB Output is correct
29 Correct 45 ms 94476 KB Output is correct
30 Correct 44 ms 94420 KB Output is correct
31 Correct 48 ms 94436 KB Output is correct
32 Correct 54 ms 94340 KB Output is correct
33 Correct 48 ms 94456 KB Output is correct
34 Correct 47 ms 94544 KB Output is correct
35 Correct 47 ms 94668 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94276 KB Output is correct
2 Correct 69 ms 99212 KB Output is correct
3 Correct 78 ms 98544 KB Output is correct
4 Correct 85 ms 103784 KB Output is correct
5 Correct 76 ms 106216 KB Output is correct
6 Correct 77 ms 106372 KB Output is correct
7 Correct 67 ms 98948 KB Output is correct
8 Correct 70 ms 98596 KB Output is correct
9 Correct 79 ms 110740 KB Output is correct
10 Correct 71 ms 97636 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94156 KB Output is correct
2 Correct 47 ms 94184 KB Output is correct
3 Correct 44 ms 94424 KB Output is correct
4 Correct 44 ms 94224 KB Output is correct
5 Correct 44 ms 94208 KB Output is correct
6 Correct 45 ms 94224 KB Output is correct
7 Correct 51 ms 94264 KB Output is correct
8 Correct 50 ms 94304 KB Output is correct
9 Correct 49 ms 94220 KB Output is correct
10 Correct 44 ms 94320 KB Output is correct
11 Correct 46 ms 94264 KB Output is correct
12 Correct 45 ms 94188 KB Output is correct
13 Correct 46 ms 94184 KB Output is correct
14 Correct 45 ms 94280 KB Output is correct
15 Correct 46 ms 94280 KB Output is correct
16 Correct 45 ms 94284 KB Output is correct
17 Correct 46 ms 94260 KB Output is correct
18 Correct 44 ms 94288 KB Output is correct
19 Correct 44 ms 94284 KB Output is correct
20 Correct 46 ms 94312 KB Output is correct
21 Correct 45 ms 94220 KB Output is correct
22 Correct 45 ms 94264 KB Output is correct
23 Correct 45 ms 94560 KB Output is correct
24 Correct 47 ms 94444 KB Output is correct
25 Correct 45 ms 94536 KB Output is correct
26 Correct 52 ms 94468 KB Output is correct
27 Correct 47 ms 94500 KB Output is correct
28 Correct 45 ms 94428 KB Output is correct
29 Correct 45 ms 94476 KB Output is correct
30 Correct 44 ms 94420 KB Output is correct
31 Correct 48 ms 94436 KB Output is correct
32 Correct 54 ms 94340 KB Output is correct
33 Correct 48 ms 94456 KB Output is correct
34 Correct 47 ms 94544 KB Output is correct
35 Correct 47 ms 94668 KB Output is correct
36 Correct 44 ms 94276 KB Output is correct
37 Correct 69 ms 99212 KB Output is correct
38 Correct 78 ms 98544 KB Output is correct
39 Correct 85 ms 103784 KB Output is correct
40 Correct 76 ms 106216 KB Output is correct
41 Correct 77 ms 106372 KB Output is correct
42 Correct 67 ms 98948 KB Output is correct
43 Correct 70 ms 98596 KB Output is correct
44 Correct 79 ms 110740 KB Output is correct
45 Correct 71 ms 97636 KB Output is correct
46 Correct 50 ms 94172 KB Output is correct
47 Correct 46 ms 94192 KB Output is correct
48 Correct 46 ms 94308 KB Output is correct
49 Correct 44 ms 94304 KB Output is correct
50 Correct 45 ms 94260 KB Output is correct
51 Correct 47 ms 94212 KB Output is correct
52 Correct 45 ms 94308 KB Output is correct
53 Correct 49 ms 94304 KB Output is correct
54 Correct 45 ms 94284 KB Output is correct
55 Correct 45 ms 94256 KB Output is correct
56 Correct 45 ms 94292 KB Output is correct
57 Correct 47 ms 94552 KB Output is correct
58 Correct 48 ms 94432 KB Output is correct
59 Correct 47 ms 94520 KB Output is correct
60 Correct 48 ms 94412 KB Output is correct
61 Correct 49 ms 94448 KB Output is correct
62 Correct 46 ms 94484 KB Output is correct
63 Correct 48 ms 94444 KB Output is correct
64 Correct 48 ms 94488 KB Output is correct
65 Correct 49 ms 94424 KB Output is correct
66 Correct 46 ms 94456 KB Output is correct
67 Correct 47 ms 94412 KB Output is correct
68 Correct 46 ms 94424 KB Output is correct
69 Correct 52 ms 94544 KB Output is correct
70 Correct 45 ms 94156 KB Output is correct
71 Correct 71 ms 99252 KB Output is correct
72 Correct 74 ms 98560 KB Output is correct
73 Correct 78 ms 103820 KB Output is correct
74 Correct 80 ms 106188 KB Output is correct
75 Correct 81 ms 106384 KB Output is correct
76 Correct 66 ms 99012 KB Output is correct
77 Correct 66 ms 98632 KB Output is correct
78 Correct 84 ms 110776 KB Output is correct
79 Correct 79 ms 97692 KB Output is correct
80 Correct 74 ms 98748 KB Output is correct
81 Correct 70 ms 99264 KB Output is correct
82 Correct 69 ms 98592 KB Output is correct
83 Correct 75 ms 101264 KB Output is correct
84 Correct 68 ms 99048 KB Output is correct
85 Correct 82 ms 106940 KB Output is correct
86 Correct 84 ms 100800 KB Output is correct
87 Correct 72 ms 98012 KB Output is correct
88 Correct 75 ms 108020 KB Output is correct
89 Correct 80 ms 110096 KB Output is correct
90 Correct 95 ms 106052 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94156 KB Output is correct
2 Correct 47 ms 94184 KB Output is correct
3 Correct 44 ms 94424 KB Output is correct
4 Correct 44 ms 94224 KB Output is correct
5 Correct 44 ms 94208 KB Output is correct
6 Correct 45 ms 94224 KB Output is correct
7 Correct 51 ms 94264 KB Output is correct
8 Correct 50 ms 94304 KB Output is correct
9 Correct 49 ms 94220 KB Output is correct
10 Correct 44 ms 94320 KB Output is correct
11 Correct 46 ms 94264 KB Output is correct
12 Correct 43 ms 94156 KB Output is correct
13 Correct 199 ms 119316 KB Output is correct
14 Correct 195 ms 113964 KB Output is correct
15 Correct 216 ms 122500 KB Output is correct
16 Correct 217 ms 123412 KB Output is correct
17 Correct 191 ms 122008 KB Output is correct
18 Correct 310 ms 201984 KB Output is correct
19 Correct 226 ms 125140 KB Output is correct
20 Correct 45 ms 94188 KB Output is correct
21 Correct 46 ms 94184 KB Output is correct
22 Correct 45 ms 94280 KB Output is correct
23 Correct 46 ms 94280 KB Output is correct
24 Correct 45 ms 94284 KB Output is correct
25 Correct 46 ms 94260 KB Output is correct
26 Correct 44 ms 94288 KB Output is correct
27 Correct 44 ms 94284 KB Output is correct
28 Correct 46 ms 94312 KB Output is correct
29 Correct 45 ms 94220 KB Output is correct
30 Correct 45 ms 94264 KB Output is correct
31 Correct 45 ms 94560 KB Output is correct
32 Correct 47 ms 94444 KB Output is correct
33 Correct 45 ms 94536 KB Output is correct
34 Correct 52 ms 94468 KB Output is correct
35 Correct 47 ms 94500 KB Output is correct
36 Correct 45 ms 94428 KB Output is correct
37 Correct 45 ms 94476 KB Output is correct
38 Correct 44 ms 94420 KB Output is correct
39 Correct 48 ms 94436 KB Output is correct
40 Correct 54 ms 94340 KB Output is correct
41 Correct 48 ms 94456 KB Output is correct
42 Correct 47 ms 94544 KB Output is correct
43 Correct 47 ms 94668 KB Output is correct
44 Correct 44 ms 94276 KB Output is correct
45 Correct 69 ms 99212 KB Output is correct
46 Correct 78 ms 98544 KB Output is correct
47 Correct 85 ms 103784 KB Output is correct
48 Correct 76 ms 106216 KB Output is correct
49 Correct 77 ms 106372 KB Output is correct
50 Correct 67 ms 98948 KB Output is correct
51 Correct 70 ms 98596 KB Output is correct
52 Correct 79 ms 110740 KB Output is correct
53 Correct 71 ms 97636 KB Output is correct
54 Correct 50 ms 94172 KB Output is correct
55 Correct 46 ms 94192 KB Output is correct
56 Correct 46 ms 94308 KB Output is correct
57 Correct 44 ms 94304 KB Output is correct
58 Correct 45 ms 94260 KB Output is correct
59 Correct 47 ms 94212 KB Output is correct
60 Correct 45 ms 94308 KB Output is correct
61 Correct 49 ms 94304 KB Output is correct
62 Correct 45 ms 94284 KB Output is correct
63 Correct 45 ms 94256 KB Output is correct
64 Correct 45 ms 94292 KB Output is correct
65 Correct 47 ms 94552 KB Output is correct
66 Correct 48 ms 94432 KB Output is correct
67 Correct 47 ms 94520 KB Output is correct
68 Correct 48 ms 94412 KB Output is correct
69 Correct 49 ms 94448 KB Output is correct
70 Correct 46 ms 94484 KB Output is correct
71 Correct 48 ms 94444 KB Output is correct
72 Correct 48 ms 94488 KB Output is correct
73 Correct 49 ms 94424 KB Output is correct
74 Correct 46 ms 94456 KB Output is correct
75 Correct 47 ms 94412 KB Output is correct
76 Correct 46 ms 94424 KB Output is correct
77 Correct 52 ms 94544 KB Output is correct
78 Correct 45 ms 94156 KB Output is correct
79 Correct 71 ms 99252 KB Output is correct
80 Correct 74 ms 98560 KB Output is correct
81 Correct 78 ms 103820 KB Output is correct
82 Correct 80 ms 106188 KB Output is correct
83 Correct 81 ms 106384 KB Output is correct
84 Correct 66 ms 99012 KB Output is correct
85 Correct 66 ms 98632 KB Output is correct
86 Correct 84 ms 110776 KB Output is correct
87 Correct 79 ms 97692 KB Output is correct
88 Correct 74 ms 98748 KB Output is correct
89 Correct 70 ms 99264 KB Output is correct
90 Correct 69 ms 98592 KB Output is correct
91 Correct 75 ms 101264 KB Output is correct
92 Correct 68 ms 99048 KB Output is correct
93 Correct 82 ms 106940 KB Output is correct
94 Correct 84 ms 100800 KB Output is correct
95 Correct 72 ms 98012 KB Output is correct
96 Correct 75 ms 108020 KB Output is correct
97 Correct 80 ms 110096 KB Output is correct
98 Correct 95 ms 106052 KB Output is correct
99 Correct 45 ms 94276 KB Output is correct
100 Correct 50 ms 94268 KB Output is correct
101 Correct 44 ms 94272 KB Output is correct
102 Correct 53 ms 94224 KB Output is correct
103 Correct 46 ms 94392 KB Output is correct
104 Correct 45 ms 94328 KB Output is correct
105 Correct 48 ms 94284 KB Output is correct
106 Correct 44 ms 94284 KB Output is correct
107 Correct 44 ms 94288 KB Output is correct
108 Correct 44 ms 94196 KB Output is correct
109 Correct 46 ms 94312 KB Output is correct
110 Correct 46 ms 94276 KB Output is correct
111 Correct 228 ms 119272 KB Output is correct
112 Correct 192 ms 113916 KB Output is correct
113 Correct 243 ms 122416 KB Output is correct
114 Correct 224 ms 123348 KB Output is correct
115 Correct 195 ms 122064 KB Output is correct
116 Correct 348 ms 201932 KB Output is correct
117 Correct 207 ms 125160 KB Output is correct
118 Correct 47 ms 94520 KB Output is correct
119 Correct 47 ms 94488 KB Output is correct
120 Correct 58 ms 94532 KB Output is correct
121 Correct 47 ms 94444 KB Output is correct
122 Correct 46 ms 94548 KB Output is correct
123 Correct 46 ms 94480 KB Output is correct
124 Correct 49 ms 94540 KB Output is correct
125 Correct 46 ms 94472 KB Output is correct
126 Correct 47 ms 94508 KB Output is correct
127 Correct 46 ms 94436 KB Output is correct
128 Correct 50 ms 94368 KB Output is correct
129 Correct 45 ms 94452 KB Output is correct
130 Correct 47 ms 94540 KB Output is correct
131 Correct 53 ms 94252 KB Output is correct
132 Correct 69 ms 99220 KB Output is correct
133 Correct 79 ms 98536 KB Output is correct
134 Correct 76 ms 103780 KB Output is correct
135 Correct 76 ms 106156 KB Output is correct
136 Correct 77 ms 106352 KB Output is correct
137 Correct 71 ms 99012 KB Output is correct
138 Correct 72 ms 98776 KB Output is correct
139 Correct 77 ms 110764 KB Output is correct
140 Correct 64 ms 97728 KB Output is correct
141 Correct 70 ms 98624 KB Output is correct
142 Correct 87 ms 99388 KB Output is correct
143 Correct 69 ms 98620 KB Output is correct
144 Correct 73 ms 101260 KB Output is correct
145 Correct 73 ms 99052 KB Output is correct
146 Correct 80 ms 106808 KB Output is correct
147 Correct 73 ms 100800 KB Output is correct
148 Correct 67 ms 98108 KB Output is correct
149 Correct 75 ms 108020 KB Output is correct
150 Correct 78 ms 110052 KB Output is correct
151 Correct 77 ms 105948 KB Output is correct
152 Correct 706 ms 198120 KB Output is correct
153 Correct 742 ms 187588 KB Output is correct
154 Correct 693 ms 172040 KB Output is correct
155 Correct 883 ms 267804 KB Output is correct
156 Correct 790 ms 215592 KB Output is correct
157 Correct 612 ms 173348 KB Output is correct
158 Correct 715 ms 229204 KB Output is correct
159 Correct 1054 ms 417556 KB Output is correct
160 Correct 1098 ms 388396 KB Output is correct
161 Correct 647 ms 169488 KB Output is correct
162 Correct 689 ms 175520 KB Output is correct