oj.uz

Submission #485894

# Submission time Handle Problem Language Result Execution time Memory
485894 2021-11-09T15:56:48 Z gavgav Fountain (eJOI20_fountain) C++17
0 / 100
 56 ms 5828 KB 
#include <stdio.h>
#define MAX_N 100000
#define MAX_M 200000
#define MAX_S 100000000000000
struct reservoir {
    long long diameters, capacity;
};
struct query {
    long long level, volume, rasp;
};
int stiva[MAX_N + 1], next[MAX_M + 1], liste[MAX_N + 1];
long long sumaNec[MAX_N + 1];
struct reservoir reservoirs[MAX_N + 1];
struct query queries[MAX_M + 1];
int main() {
    int height, queries_number, top, st, dr, mij, i, j;
    long long sumaV;
    scanf( "%d%d", &height, &queries_number);
    reservoirs[0].diameters = 1000000001;
    reservoirs[0].capacity = 0;
    for ( i = 1; i <= height; ++i)
        scanf( "%lld%lld", &reservoirs[i].diameters, &reservoirs[i].capacity);
    for ( 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;
    }
    stiva[0] = 0;
    sumaNec[0] = -MAX_S - 1;
    top = 0;
    sumaV = 0;
    for ( i = height; i >= 1; --i) {
        while ( reservoirs[i].diameters >= reservoirs[stiva[top]].diameters ) {
            sumaV -= reservoirs[stiva[top]].capacity;
            --top;
        }
        --top;
        stiva[top] = i;
        sumaNec[top] = sumaV;
        sumaV += reservoirs[i].capacity;

        j = liste[i];
        while ( j != 0 ) {
            st = top + 1;
            dr = 0;
            while ( st - dr > 1 ) {
                mij = (st + dr) / 2;
                if ( sumaV - sumaNec[mij] >= queries[j].volume)
                    dr = mij;
                else
                    st = mij;
            }
            queries[j].rasp = stiva[dr];

            j = next[j];
        }
    }
    for ( i = 1; i <= queries_number; ++i)
        printf( "%lld\n", queries[i].rasp );
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf( "%d%d", &height, &queries_number);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf( "%lld%lld", &reservoirs[i].diameters, &reservoirs[i].capacity);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf( "%lld%lld", &queries[i].level, &queries[i].volume);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:38:18: warning: array subscript -1 is below array bounds of 'int [100001]' [-Warray-bounds]
   38 |         stiva[top] = i;
      |         ~~~~~~~~~^
fountain.cpp:11:5: note: while referencing 'stiva'
   11 | int stiva[MAX_N + 1], next[MAX_M + 1], liste[MAX_N + 1];
      |     ^~~~~
fountain.cpp:39:20: warning: array subscript -1 is below array bounds of 'long long int [100001]' [-Warray-bounds]
   39 |         sumaNec[top] = sumaV;
      |         ~~~~~~~~~~~^
fountain.cpp:12:11: note: while referencing 'sumaNec'
   12 | long long sumaNec[MAX_N + 1];
      |           ^~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 5828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -