oj.uz

Submission #469209

# Submission time Handle Problem Language Result Execution time Memory
469209 2021-08-31T06:15:41 Z gavgav Fountain (eJOI20_fountain) C++17
60 / 100
 769 ms 524292 KB 
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main(){
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    /*
     * Get dates about fountain.
     * Creating array in witch every number denotes index of the nearest number witch greater than this reservoir.
     * Indexes in this array means number of reservoir.
     */
    int streams_number = 0, queries, height;
    scanf("%d%d", &height, &queries);
    int diameters[height], next_grater[height], capacities[height + 1];
    capacities[height] = 0;
    vector <int> starts;
    stack <int> meowmeow;
    for (int i = 0; i < height; i++){
        scanf("%d%d", &diameters[i], &capacities[i]);
        if (!meowmeow.empty() && diameters[i] > diameters[meowmeow.top()]){
            do{
                next_grater[meowmeow.top()] = i;
                meowmeow.pop();
            }while (!meowmeow.empty() && diameters[i] > diameters[meowmeow.top()]);
        }
        else{
            streams_number++;
            starts.push_back(i);
        }
        meowmeow.push(i);
    }
    while (!meowmeow.empty()){
        next_grater[meowmeow.top()] = height;
        meowmeow.pop();
    }
    /*
     * Creating of any possible water path.
     */
    int affiliation[height], indexes[height];
    int lengths[streams_number] {};
    vector <long long> streams[streams_number];
    for (int i = 0; i < streams_number; i++){
        for (int j = starts[i], k = 0; j != height; j = next_grater[j], k++) {
            streams[i].push_back(j);
            lengths[i]++;
            indexes[j] = k;
            affiliation[j] = i;
        }
        streams[i].push_back(height);
    }
    /*
     * Creating postfix sums array.
     */
    for (int i = height - 1; i > -1; i--){
        capacities[i] += capacities[next_grater[i]];
    }
    /*
     * Get queries and by binary search print answer.
     */

    int volume, level, left, right, middle, answer;
    while (queries--){
        scanf("%d%d", &level, &volume);
        level--;
        left = indexes[level] + 1, right = lengths[affiliation[level]], answer = streams[affiliation[level]][indexes[level]] + 1;
        while (left - right < 1){
            middle = (left + right) / 2;
            if (volume > capacities[level] - capacities[streams[affiliation[level]][middle]]){
                answer = streams[affiliation[level]][middle] + 1;
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        printf("%d\n", answer % (height + 1));
    }
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d%d", &height, &queries);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf("%d%d", &diameters[i], &capacities[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf("%d%d", &level, &volume);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 3640 KB Output is correct
2 Correct 115 ms 3644 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 101 ms 3640 KB Output is correct
9 Correct 115 ms 3644 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Runtime error 769 ms 524292 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -