Submission #485883

#	Time	Username	Problem	Language	Result	Execution time	Memory
485883		gavgav	Fountain (eJOI20_fountain)	C++17	0 / 100	52 ms	16072 KiB

fountain

#include <stdio.h>
#define MAX_N 100000
#define MAX_M 200000
#define MAX_S 100000000000000
struct reservoir {
    long long diameter, capacity;
};
struct query{
    long long level, volume, rasp;
};
long long next[MAX_M + 1], liste[MAX_N + 1];
long long sumaNec[MAX_N + 1];
int main() {
    long long height, queries_number, top, j;
    long long sumaV;
    scanf( "%lld%lld", &height, &queries_number );
    long long stack[height];
    struct reservoir reservoirs[height];
    struct query queries[queries_number];
    reservoirs[0].diameter = 1000000001;
    reservoirs[0].capacity = 0;
    for (long long i = 1; i <= height; ++i)
        scanf( "%lld%lld", &reservoirs[i].diameter, &reservoirs[i].capacity);
    for (long long i = 1; i <= queries_number; i++ ) {
        scanf( "%lld%lld", &queries[i].level, &queries[i].volume);
        next[i] = liste[queries[i].level];
        liste[queries[i].level] = i;
    }
    stack[0] = 0;
    sumaNec[0] = -MAX_S - 1;
    top = 0;
    sumaV = 0;
    long long left, right, middle;
    for (long long i = height; i >= 1; --i) {
        while ( reservoirs[i].diameter >= reservoirs[stack[top]].diameter) {
            sumaV -= reservoirs[stack[top]].capacity;
            --top;
        }
        ++top;
        stack[top] = i;
        sumaNec[top] = sumaV;
        sumaV += reservoirs[i].capacity;
        j = liste[i];
        while ( j != 0 ) {
            right = top + 1;
            left = 0;
            while ( right - left > 1 ) {
                middle = (right + left) / 2;
                if ( sumaV - sumaNec[middle] >= queries[j].volume){
                    left = middle;
                }
                else{
                    right = middle;
                }
            }
            queries[j].rasp = stack[left];
            j = next[j];
        }
    }
    for (long long i = 1; i <= queries_number; ++i)
        printf( "%d\n", queries[i].rasp);
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:61:19: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   61 |         printf( "%d\n", queries[i].rasp);
      |                  ~^     ~~~~~~~~~~~~~~~
      |                   |                |
      |                   int              long long int
      |                  %lld
fountain.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf( "%lld%lld", &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( "%lld%lld", &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( "%lld%lld", &queries[i].level, &queries[i].volume);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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