Submission #504134

#	Time	Username	Problem	Language	Result	Execution time	Memory
504134		gavgav	Fountain (eJOI20_fountain)	C++17	100 / 100	105 ms	10464 KiB

fountain

// This is Lucallie's solving but with some optimizations and explanations, 'cause when I solved this problem with own code I wondered why this solving is so fast and try to understand it, but he's code is weird and strange, but super fast.
#include <bits/stdc++.h>
using namespace std;
struct reservoir{
    int diameter;
    short capacity; // 1 <= diameter <= 10^9 | 1 <= capacity <= 1000
};
struct query{
    int level, volume, answer; // 1 <= volume <= 10^9
};
int main() {
    int height, queries_number, necessary, top, i, j; // 2 <= height <= 10^5 | 1 <= queries 2 * 10^5
    scanf( "%d%d", &height, &queries_number);
    int previous_request[queries_number + 1], // i-th number of previous_request keeps index of previous request that opened tap of this request
        last_request[height + 1] {}, // i-th number of last_request keeps index of last query that open tap at i-th reservoir
        necessary_water[height + 1], // i-th number of necessary_water keeps volume of water which need to reach waterways from i-th + 1 reservoir
        stream[height + 1];
    reservoir reservoirs[height + 1];
    query queries[queries_number + 1];
    reservoirs[0].diameter = 1000000001; // maximum possible diameter + 1
    reservoirs[0].capacity = 0;
    for (i = 1; i <= height; ++i)
        scanf( "%d%hd", &reservoirs[i].diameter, &reservoirs[i].capacity);
    for (i = 1; i <= queries_number; ++i) {
        scanf( "%d%d", &queries[i].level, &queries[i].volume);
        previous_request[i] = last_request[queries[i].level];
        last_request[queries[i].level] = i;
    }
    stream[0] = 0;
    top = 0;
    necessary = 0;
    int left, middle, right;
    for (i = height; i > 0; --i) {
        while (reservoirs[i].diameter >= reservoirs[stream[top]].diameter) {
            necessary -= reservoirs[stream[top]].capacity;
            --top;
        }
        ++top;
        stream[top] = i;
        necessary_water[top] = necessary;
        necessary += reservoirs[i].capacity;
        j = last_request[i];
        while (j != 0) {
            right = top + 1;
            left = 0;
            while (right - left > 1 ) {
                middle = (right + left) / 2;
                if (necessary - necessary_water[middle] >= queries[j].volume)
                    left = middle;
                else
                    right = middle;
            }
            queries[j].answer = stream[left];
            j = previous_request[j];
        }
    }
    for (i = 1; i <= queries_number; ++i){
        printf("%d\n", queries[i].answer);
    }
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf( "%d%d", &height, &queries_number);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf( "%d%hd", &reservoirs[i].diameter, &reservoirs[i].capacity);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf( "%d%d", &queries[i].level, &queries[i].volume);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40