Submission #1028332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028332		Swee	Pilot (NOI19_pilot)	C++14	89 / 100	1093 ms	42160 KiB

pilot

#include <iostream>
#include <vector>

using namespace std;

struct mountain {
    int height;
    int index;
};

vector<long long> count(vector<int> h, int n, vector<int> y, int q) {
    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(); ) {
        if (h[i] >= border.back().height) { // 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.pop_back();
        }else {
            border.push_back({h[i], i}); // add border
            i++;
        }
    }

    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, n, y, q);

    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << endl;
    }

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 0 / 11