oj.uz

Submission #1028343

# Submission time Handle Problem Language Result Execution time Memory
1028343 2024-07-19T16:57:04 Z Swee Pilot (NOI19_pilot) C++14
40 / 100
 137 ms 12288 KB 
#include <iostream>
#include <vector>

using namespace std;

struct mountain {
    int height;
    int index;
};

vector<long long> count(vector<int> h, vector<int> y) {
    h.push_back(1000001); // last border

    vector<mountain> border;
    border.push_back({1000002, -1}); // blocker 

    vector<long long> allPlanes(1000001);
    for (int i = 0; i < h.size(); i++) {
        for (;h[i] >= border.back().height; border.pop_back()) { // remove last border
            long long a = (i - border.back().index), b = (border.back().index - border[border.size() - 2].index);
            allPlanes[border.back().height] += a * b; // add possible flights to last border mountain height velocity plane
            // starting before or with last border * ending after or with last border
        }
        border.push_back({h[i], i}); // add border
    }

    for (int i = 2; i < allPlanes.size(); i++) { // partial sum of possible flights
        allPlanes[i] += allPlanes[i - 1];
    }

    vector<long long> result;

    for (int Y : y) { // filling up queries
        if (Y >= allPlanes.size()) {
            result.push_back(allPlanes.back());
        }else {
            result.push_back(allPlanes[Y]);
        }
    }

    return result;
}

int main() {
    int n, q;
    cin >> n >> q;

    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    vector<int> y(q);
    for (int i = 0; i < q; i++) {
        cin >> y[i];
    }

    vector<long long> result = count(h, y);

    for (int r : result) {
        cout << r << endl;
    }

    return 0;
}

Compilation message

pilot.cpp: In function 'std::vector<long long int> count(std::vector<int>, std::vector<int>)':
pilot.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0; i < h.size(); i++) {
      |                     ~~^~~~~~~~~~
pilot.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i = 2; i < allPlanes.size(); i++) { // partial sum of possible flights
      |                     ~~^~~~~~~~~~~~~~~~~~
pilot.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         if (Y >= allPlanes.size()) {
      |             ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8024 KB Output is correct
2 Correct 4 ms 8028 KB Output is correct
3 Correct 4 ms 8056 KB Output is correct
4 Correct 4 ms 8028 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 4 ms 8116 KB Output is correct
8 Correct 4 ms 8028 KB Output is correct
9 Correct 4 ms 8280 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8024 KB Output is correct
2 Correct 4 ms 8028 KB Output is correct
3 Correct 4 ms 8056 KB Output is correct
4 Correct 4 ms 8028 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 4 ms 8116 KB Output is correct
8 Correct 4 ms 8028 KB Output is correct
9 Correct 4 ms 8280 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Correct 4 ms 8028 KB Output is correct
12 Correct 4 ms 8028 KB Output is correct
13 Correct 4 ms 8028 KB Output is correct
14 Correct 4 ms 8028 KB Output is correct
15 Correct 4 ms 8244 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8024 KB Output is correct
2 Correct 4 ms 8028 KB Output is correct
3 Correct 4 ms 8056 KB Output is correct
4 Correct 4 ms 8028 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 4 ms 8116 KB Output is correct
8 Correct 4 ms 8028 KB Output is correct
9 Correct 4 ms 8280 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Correct 4 ms 8028 KB Output is correct
12 Correct 4 ms 8028 KB Output is correct
13 Correct 4 ms 8028 KB Output is correct
14 Correct 4 ms 8028 KB Output is correct
15 Correct 4 ms 8244 KB Output is correct
16 Correct 5 ms 8280 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct
18 Correct 4 ms 8284 KB Output is correct
19 Correct 4 ms 8284 KB Output is correct
20 Correct 4 ms 8280 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8024 KB Output is correct
2 Correct 4 ms 8028 KB Output is correct
3 Correct 4 ms 8056 KB Output is correct
4 Correct 4 ms 8028 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 4 ms 8116 KB Output is correct
8 Correct 4 ms 8028 KB Output is correct
9 Correct 4 ms 8280 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Correct 4 ms 8028 KB Output is correct
12 Correct 4 ms 8028 KB Output is correct
13 Correct 4 ms 8028 KB Output is correct
14 Correct 4 ms 8028 KB Output is correct
15 Correct 4 ms 8244 KB Output is correct
16 Correct 5 ms 8280 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct
18 Correct 4 ms 8284 KB Output is correct
19 Correct 4 ms 8284 KB Output is correct
20 Correct 4 ms 8280 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 5 ms 8284 KB Output is correct
23 Correct 5 ms 8284 KB Output is correct
24 Correct 5 ms 8284 KB Output is correct
25 Correct 5 ms 8072 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 9376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 12256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 137 ms 12288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8024 KB Output is correct
2 Correct 4 ms 8028 KB Output is correct
3 Correct 4 ms 8056 KB Output is correct
4 Correct 4 ms 8028 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 4 ms 8116 KB Output is correct
8 Correct 4 ms 8028 KB Output is correct
9 Correct 4 ms 8280 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Incorrect 38 ms 9376 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8024 KB Output is correct
2 Correct 4 ms 8028 KB Output is correct
3 Correct 4 ms 8056 KB Output is correct
4 Correct 4 ms 8028 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 4 ms 8116 KB Output is correct
8 Correct 4 ms 8028 KB Output is correct
9 Correct 4 ms 8280 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Correct 4 ms 8028 KB Output is correct
12 Correct 4 ms 8028 KB Output is correct
13 Correct 4 ms 8028 KB Output is correct
14 Correct 4 ms 8028 KB Output is correct
15 Correct 4 ms 8244 KB Output is correct
16 Correct 5 ms 8280 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct
18 Correct 4 ms 8284 KB Output is correct
19 Correct 4 ms 8284 KB Output is correct
20 Correct 4 ms 8280 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 5 ms 8284 KB Output is correct
23 Correct 5 ms 8284 KB Output is correct
24 Correct 5 ms 8284 KB Output is correct
25 Correct 5 ms 8072 KB Output is correct
26 Incorrect 38 ms 9376 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8024 KB Output is correct
2 Correct 4 ms 8028 KB Output is correct
3 Correct 4 ms 8056 KB Output is correct
4 Correct 4 ms 8028 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 4 ms 8116 KB Output is correct
8 Correct 4 ms 8028 KB Output is correct
9 Correct 4 ms 8280 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Correct 4 ms 8028 KB Output is correct
12 Correct 4 ms 8028 KB Output is correct
13 Correct 4 ms 8028 KB Output is correct
14 Correct 4 ms 8028 KB Output is correct
15 Correct 4 ms 8244 KB Output is correct
16 Correct 5 ms 8280 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct
18 Correct 4 ms 8284 KB Output is correct
19 Correct 4 ms 8284 KB Output is correct
20 Correct 4 ms 8280 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 5 ms 8284 KB Output is correct
23 Correct 5 ms 8284 KB Output is correct
24 Correct 5 ms 8284 KB Output is correct
25 Correct 5 ms 8072 KB Output is correct
26 Incorrect 38 ms 9376 KB Output isn't correct
27 Halted 0 ms 0 KB -