oj.uz

Submission #439087

# Submission time Handle Problem Language Result Execution time Memory
439087 2021-06-29T07:44:33 Z Hausdorf Solar Storm (NOI20_solarstorm) C++17
100 / 100
 1414 ms 238524 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define itn int
#define fi first
#define se second
#pragma optimization ("O3")
#pragma GCC target ("avx2")
#pragma optimization ("unroll_loops")
int maxn = 1e6 + 50;
vector<vector<ll>> go(maxn, vector<ll> (21));
vector<int> d(maxn), v(maxn);
vector<ll> presum(maxn), h(maxn);
bool isdeeper (int a, int b) { // true if a is deeper
    return h[a] >= h[b];
}
int binlift (int a, int k) {
    for (int l = 20; l >= 0; --l) {
        if (k & (1 << l)) {
            a = go[a][l];
        }
    }
    return a;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, s; ll k; cin >> n >> s >> k;
    for (int i = 1; i < n; ++i)
        cin >> d[i];
    for (int i = 1; i <= n; ++i)
        cin >> v[i];
    presum[0] = 0;
    h[1] = 0;
    for (int i = 1; i <= n; ++i)
        presum[i] = presum[i - 1] + v[i];
    for (int i = 2; i <= n; ++i) {
        h[i] = h[i - 1] + d[i - 1];
        //cout << h[i] << ' ';
    } //cout << endl;
    go[n][0] = n + 1;
    go[n + 1][0] = n + 1;
    for (int i = 1; i < n; ++i) {
        int j = (int) (upper_bound(h.begin() + 1, h.begin() + n + 1, h[i] + k) - h.begin() - 1);
        //cout << i << ' ' << j << endl;
        j = (int) (upper_bound(h.begin() + 1, h.begin() + n + 1, h[j] + k) - h.begin() - 1);
        //cout << i << ' ' << j << endl;
        go[i][0] = j + 1;
    }
    for (int l = 1; l <= 20; ++l) {
        for (int i = 1; i <= n + 1; ++i) {
            go[i][l] = go[go[i][l - 1]][l - 1];
        }
    }
    ll ans = -1;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, presum[binlift(i, s) - 1] - presum[i - 1]);
    }
    //cout << ans << endl;
    for (int i = 1; i <= n; ++i) {
        if (ans == presum[binlift(i, s) - 1] - presum[i - 1]) {
            vector<int> shields;
            for (int j = i; j <= n && shields.size() < s; j = go[j][0]) {
                shields.push_back((int) (upper_bound(h.begin() + 1, h.begin() + n + 1, h[j] + k) - h.begin() - 1));
            }
            cout << shields.size() << '\n';
            for (int elem : shields)
                cout << elem << ' ';
            break;
        }
    }
}

Compilation message

SolarStorm.cpp:8: warning: ignoring '#pragma optimization ' [-Wunknown-pragmas]
    8 | #pragma optimization ("O3")
      | 
SolarStorm.cpp:10: warning: ignoring '#pragma optimization ' [-Wunknown-pragmas]
   10 | #pragma optimization ("unroll_loops")
      | 
SolarStorm.cpp: In function 'int main()':
SolarStorm.cpp:64:54: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |             for (int j = i; j <= n && shields.size() < s; j = go[j][0]) {
      |                                       ~~~~~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 219452 KB Output is correct
2 Correct 204 ms 219608 KB Output is correct
3 Correct 176 ms 219544 KB Output is correct
4 Correct 180 ms 219544 KB Output is correct
5 Correct 174 ms 219524 KB Output is correct
6 Correct 194 ms 219476 KB Output is correct
7 Correct 175 ms 219584 KB Output is correct
8 Correct 168 ms 219548 KB Output is correct
9 Correct 169 ms 219460 KB Output is correct
10 Correct 196 ms 219544 KB Output is correct
11 Correct 176 ms 219584 KB Output is correct
12 Correct 205 ms 219528 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 219548 KB Output is correct
2 Correct 540 ms 219504 KB Output is correct
3 Correct 567 ms 219596 KB Output is correct
4 Correct 615 ms 219504 KB Output is correct
5 Correct 715 ms 219460 KB Output is correct
6 Correct 896 ms 219500 KB Output is correct
7 Correct 614 ms 219508 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 219452 KB Output is correct
2 Correct 204 ms 219608 KB Output is correct
3 Correct 176 ms 219544 KB Output is correct
4 Correct 180 ms 219544 KB Output is correct
5 Correct 174 ms 219524 KB Output is correct
6 Correct 194 ms 219476 KB Output is correct
7 Correct 175 ms 219584 KB Output is correct
8 Correct 168 ms 219548 KB Output is correct
9 Correct 169 ms 219460 KB Output is correct
10 Correct 196 ms 219544 KB Output is correct
11 Correct 176 ms 219584 KB Output is correct
12 Correct 205 ms 219528 KB Output is correct
13 Correct 628 ms 219548 KB Output is correct
14 Correct 540 ms 219504 KB Output is correct
15 Correct 567 ms 219596 KB Output is correct
16 Correct 615 ms 219504 KB Output is correct
17 Correct 715 ms 219460 KB Output is correct
18 Correct 896 ms 219500 KB Output is correct
19 Correct 614 ms 219508 KB Output is correct
20 Correct 519 ms 226820 KB Output is correct
21 Correct 656 ms 227648 KB Output is correct
22 Correct 730 ms 227648 KB Output is correct
23 Correct 656 ms 227660 KB Output is correct
24 Correct 639 ms 227760 KB Output is correct
25 Correct 675 ms 227808 KB Output is correct
26 Correct 525 ms 226988 KB Output is correct
27 Correct 686 ms 227780 KB Output is correct
28 Correct 674 ms 227772 KB Output is correct
29 Correct 846 ms 227528 KB Output is correct
30 Correct 685 ms 227652 KB Output is correct
31 Correct 664 ms 227716 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 876 ms 226412 KB Output is correct
2 Correct 628 ms 219768 KB Output is correct
3 Correct 619 ms 219496 KB Output is correct
4 Correct 767 ms 219504 KB Output is correct
5 Correct 717 ms 219504 KB Output is correct
6 Correct 777 ms 219568 KB Output is correct
7 Correct 1331 ms 225328 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 219452 KB Output is correct
2 Correct 204 ms 219608 KB Output is correct
3 Correct 176 ms 219544 KB Output is correct
4 Correct 180 ms 219544 KB Output is correct
5 Correct 174 ms 219524 KB Output is correct
6 Correct 194 ms 219476 KB Output is correct
7 Correct 175 ms 219584 KB Output is correct
8 Correct 168 ms 219548 KB Output is correct
9 Correct 169 ms 219460 KB Output is correct
10 Correct 196 ms 219544 KB Output is correct
11 Correct 176 ms 219584 KB Output is correct
12 Correct 205 ms 219528 KB Output is correct
13 Correct 241 ms 219628 KB Output is correct
14 Correct 179 ms 219680 KB Output is correct
15 Correct 202 ms 219492 KB Output is correct
16 Correct 191 ms 219464 KB Output is correct
17 Correct 197 ms 219568 KB Output is correct
18 Correct 205 ms 219696 KB Output is correct
19 Correct 222 ms 219496 KB Output is correct
20 Correct 178 ms 219548 KB Output is correct
21 Correct 180 ms 219740 KB Output is correct
22 Correct 201 ms 219560 KB Output is correct
23 Correct 188 ms 219560 KB Output is correct
24 Correct 178 ms 219560 KB Output is correct
25 Correct 190 ms 219592 KB Output is correct
26 Correct 169 ms 219544 KB Output is correct
27 Correct 181 ms 219608 KB Output is correct
28 Correct 182 ms 219608 KB Output is correct
29 Correct 175 ms 219588 KB Output is correct
30 Correct 195 ms 219524 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 219452 KB Output is correct
2 Correct 204 ms 219608 KB Output is correct
3 Correct 176 ms 219544 KB Output is correct
4 Correct 180 ms 219544 KB Output is correct
5 Correct 174 ms 219524 KB Output is correct
6 Correct 194 ms 219476 KB Output is correct
7 Correct 175 ms 219584 KB Output is correct
8 Correct 168 ms 219548 KB Output is correct
9 Correct 169 ms 219460 KB Output is correct
10 Correct 196 ms 219544 KB Output is correct
11 Correct 176 ms 219584 KB Output is correct
12 Correct 205 ms 219528 KB Output is correct
13 Correct 628 ms 219548 KB Output is correct
14 Correct 540 ms 219504 KB Output is correct
15 Correct 567 ms 219596 KB Output is correct
16 Correct 615 ms 219504 KB Output is correct
17 Correct 715 ms 219460 KB Output is correct
18 Correct 896 ms 219500 KB Output is correct
19 Correct 614 ms 219508 KB Output is correct
20 Correct 519 ms 226820 KB Output is correct
21 Correct 656 ms 227648 KB Output is correct
22 Correct 730 ms 227648 KB Output is correct
23 Correct 656 ms 227660 KB Output is correct
24 Correct 639 ms 227760 KB Output is correct
25 Correct 675 ms 227808 KB Output is correct
26 Correct 525 ms 226988 KB Output is correct
27 Correct 686 ms 227780 KB Output is correct
28 Correct 674 ms 227772 KB Output is correct
29 Correct 846 ms 227528 KB Output is correct
30 Correct 685 ms 227652 KB Output is correct
31 Correct 664 ms 227716 KB Output is correct
32 Correct 699 ms 227600 KB Output is correct
33 Correct 607 ms 227656 KB Output is correct
34 Correct 868 ms 227656 KB Output is correct
35 Correct 627 ms 226856 KB Output is correct
36 Correct 622 ms 227432 KB Output is correct
37 Correct 713 ms 227688 KB Output is correct
38 Correct 945 ms 227656 KB Output is correct
39 Correct 748 ms 227708 KB Output is correct
40 Correct 883 ms 227728 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 219452 KB Output is correct
2 Correct 204 ms 219608 KB Output is correct
3 Correct 176 ms 219544 KB Output is correct
4 Correct 180 ms 219544 KB Output is correct
5 Correct 174 ms 219524 KB Output is correct
6 Correct 194 ms 219476 KB Output is correct
7 Correct 175 ms 219584 KB Output is correct
8 Correct 168 ms 219548 KB Output is correct
9 Correct 169 ms 219460 KB Output is correct
10 Correct 196 ms 219544 KB Output is correct
11 Correct 176 ms 219584 KB Output is correct
12 Correct 205 ms 219528 KB Output is correct
13 Correct 628 ms 219548 KB Output is correct
14 Correct 540 ms 219504 KB Output is correct
15 Correct 567 ms 219596 KB Output is correct
16 Correct 615 ms 219504 KB Output is correct
17 Correct 715 ms 219460 KB Output is correct
18 Correct 896 ms 219500 KB Output is correct
19 Correct 614 ms 219508 KB Output is correct
20 Correct 519 ms 226820 KB Output is correct
21 Correct 656 ms 227648 KB Output is correct
22 Correct 730 ms 227648 KB Output is correct
23 Correct 656 ms 227660 KB Output is correct
24 Correct 639 ms 227760 KB Output is correct
25 Correct 675 ms 227808 KB Output is correct
26 Correct 525 ms 226988 KB Output is correct
27 Correct 686 ms 227780 KB Output is correct
28 Correct 674 ms 227772 KB Output is correct
29 Correct 846 ms 227528 KB Output is correct
30 Correct 685 ms 227652 KB Output is correct
31 Correct 664 ms 227716 KB Output is correct
32 Correct 876 ms 226412 KB Output is correct
33 Correct 628 ms 219768 KB Output is correct
34 Correct 619 ms 219496 KB Output is correct
35 Correct 767 ms 219504 KB Output is correct
36 Correct 717 ms 219504 KB Output is correct
37 Correct 777 ms 219568 KB Output is correct
38 Correct 1331 ms 225328 KB Output is correct
39 Correct 241 ms 219628 KB Output is correct
40 Correct 179 ms 219680 KB Output is correct
41 Correct 202 ms 219492 KB Output is correct
42 Correct 191 ms 219464 KB Output is correct
43 Correct 197 ms 219568 KB Output is correct
44 Correct 205 ms 219696 KB Output is correct
45 Correct 222 ms 219496 KB Output is correct
46 Correct 178 ms 219548 KB Output is correct
47 Correct 180 ms 219740 KB Output is correct
48 Correct 201 ms 219560 KB Output is correct
49 Correct 188 ms 219560 KB Output is correct
50 Correct 178 ms 219560 KB Output is correct
51 Correct 190 ms 219592 KB Output is correct
52 Correct 169 ms 219544 KB Output is correct
53 Correct 181 ms 219608 KB Output is correct
54 Correct 182 ms 219608 KB Output is correct
55 Correct 175 ms 219588 KB Output is correct
56 Correct 195 ms 219524 KB Output is correct
57 Correct 699 ms 227600 KB Output is correct
58 Correct 607 ms 227656 KB Output is correct
59 Correct 868 ms 227656 KB Output is correct
60 Correct 627 ms 226856 KB Output is correct
61 Correct 622 ms 227432 KB Output is correct
62 Correct 713 ms 227688 KB Output is correct
63 Correct 945 ms 227656 KB Output is correct
64 Correct 748 ms 227708 KB Output is correct
65 Correct 883 ms 227728 KB Output is correct
66 Correct 558 ms 227500 KB Output is correct
67 Correct 926 ms 232432 KB Output is correct
68 Correct 659 ms 232676 KB Output is correct
69 Correct 993 ms 230160 KB Output is correct
70 Correct 556 ms 227652 KB Output is correct
71 Correct 893 ms 227656 KB Output is correct
72 Correct 639 ms 227780 KB Output is correct
73 Correct 855 ms 227772 KB Output is correct
74 Correct 577 ms 226364 KB Output is correct
75 Correct 803 ms 227656 KB Output is correct
76 Correct 603 ms 227396 KB Output is correct
77 Correct 722 ms 227656 KB Output is correct
78 Correct 607 ms 227008 KB Output is correct
79 Correct 672 ms 227776 KB Output is correct
80 Correct 1006 ms 227708 KB Output is correct
81 Correct 531 ms 227564 KB Output is correct
82 Correct 699 ms 227652 KB Output is correct
83 Correct 529 ms 226268 KB Output is correct
84 Correct 557 ms 226848 KB Output is correct
85 Correct 579 ms 226368 KB Output is correct
86 Correct 859 ms 227648 KB Output is correct
87 Correct 559 ms 226508 KB Output is correct
88 Correct 812 ms 227704 KB Output is correct
89 Correct 715 ms 227648 KB Output is correct
90 Correct 655 ms 227780 KB Output is correct
91 Correct 1131 ms 238524 KB Output is correct
92 Correct 1064 ms 228452 KB Output is correct
93 Correct 1414 ms 233400 KB Output is correct
94 Correct 1207 ms 233428 KB Output is correct
95 Correct 809 ms 227624 KB Output is correct
96 Correct 706 ms 227748 KB Output is correct
97 Correct 930 ms 228684 KB Output is correct
98 Correct 656 ms 230212 KB Output is correct
99 Correct 801 ms 234684 KB Output is correct
100 Correct 795 ms 234704 KB Output is correct