oj.uz

Submission #485817

# Submission time Handle Problem Language Result Execution time Memory
485817 2021-11-09T12:55:28 Z gavgav Fountain (eJOI20_fountain) C++17
100 / 100
 430 ms 28840 KB 
#include <iostream>
#include <vector>
using namespace std;
int main(){
    long long height, queries;
    scanf("%lld%lld", &height, &queries);
    long long diameters[height], postfix_sum[height + 1], stack[height] {}, top = -1;
    postfix_sum[height] = 0;
    vector <long long> jumps[height + 1];
    for (long long i = 0; i < height; ++i){
        scanf("%lld%lld", diameters + i, postfix_sum + i);
        while (top != -1 && diameters[stack[top]] < diameters[i]){
           jumps[stack[top]].push_back(i);
            --top;
        }
        ++top;
        stack[top] = i;
    }
    while (top != -1){
        jumps[stack[top]].push_back(height);
        --top;
    }
    for (long long i = height - 2; i > -1; --i){
        postfix_sum[i] += postfix_sum[jumps[i][0]];
        for (long long j = 0; jumps[jumps[i][j]].size() > j; ++j){
            jumps[i].push_back(jumps[jumps[i][j]][j]);
        }
    }
    long long level, volume;
    while (queries){
        scanf("%lld%lld", &level, &volume);
        --level;
        long long i ;
        while (true){
            i = jumps[level].size() - 1;
            for (; i > -1 && volume <= postfix_sum[level] - postfix_sum[jumps[level][i]]; --i);
            if (i == -1){
                break;
            }
            volume -= postfix_sum[level] - postfix_sum[jumps[level][i]];
            level = jumps[level][i];
        }
        printf("%lld\n", (level + 1) % (height + 1));
        --queries;
    }
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:25:57: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   25 |         for (long long j = 0; jumps[jumps[i][j]].size() > j; ++j){
      |                               ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
fountain.cpp:6:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |     scanf("%lld%lld", &height, &queries);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         scanf("%lld%lld", diameters + i, postfix_sum + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%lld%lld", &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 304 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 460 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 286 ms 25484 KB Output is correct
2 Correct 263 ms 23296 KB Output is correct

Subtask #3
40.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 304 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 286 ms 25484 KB Output is correct
9 Correct 263 ms 23296 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 109 ms 12948 KB Output is correct
12 Correct 430 ms 28840 KB Output is correct
13 Correct 279 ms 23940 KB Output is correct
14 Correct 139 ms 15728 KB Output is correct
15 Correct 93 ms 13288 KB Output is correct