Submission #485817

#	Time	Username	Problem	Language	Result	Execution time	Memory
485817		gavgav	Fountain (eJOI20_fountain)	C++17	100 / 100	430 ms	28840 KiB

fountain

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40