oj.uz

Submission #485818

# Submission time Handle Problem Language Result Execution time Memory
485818 2021-11-09T12:57:24 Z gavgav Fountain (eJOI20_fountain) C++17
100 / 100
 380 ms 24572 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 1 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 2 ms 460 KB Output is correct
6 Correct 2 ms 332 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 240 ms 22492 KB Output is correct
2 Correct 316 ms 20300 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 460 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 240 ms 22492 KB Output is correct
9 Correct 316 ms 20300 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 91 ms 11272 KB Output is correct
12 Correct 380 ms 24572 KB Output is correct
13 Correct 266 ms 20420 KB Output is correct
14 Correct 126 ms 12716 KB Output is correct
15 Correct 91 ms 10052 KB Output is correct