제출 #485899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
485899		gavgav	Fountain (eJOI20_fountain)	C++17	100 / 100	109 ms	7404 KiB

fountain

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

컴파일 시 표준 에러 (stderr) 메시지

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( "%lld%lld", &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( "%d%d", &q[i].level, &q[i].volume);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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