oj.uz

Submission #485888

# Submission time Handle Problem Language Result Execution time Memory
485888 2021-11-09T15:49:45 Z gavgav Fountain (eJOI20_fountain) C++17
100 / 100
 107 ms 6588 KB 
#include <stdio.h>
#define MAX_N 100000
#define MAX_M 200000
#define MAX_D 1000000000
#define MAX_S 100000000000000
struct rezervor {
    int d, v;
};
struct query {
    int s, v, rasp;
};
int stiva[MAX_N + 1], next[MAX_M + 1], liste[MAX_N + 1];
long long sumaNec[MAX_N + 1];
struct rezervor rez[MAX_N + 1];
struct query q[MAX_M + 1];
int main() {
    int height, queries_number, top, st, dr, mij, i, j;
    long long sumaV;
    scanf( "%d%d", &height, &queries_number);
    rez[0].d = MAX_D + 1;
    rez[0].v = 0;
    for ( i = 1; i <= height; i++ )
        scanf( "%d%d", &rez[i].d, &rez[i].v );
    for ( i = 1; i <= queries_number; i++ ) {
        scanf( "%d%d", &q[i].s, &q[i].v );
        next[i] = liste[q[i].s];
        liste[q[i].s] = i;
    }
    stiva[0] = 0;
    sumaNec[0] = -MAX_S - 1;
    top = 0;
    sumaV = 0;
    for ( i = height; i >= 1; i-- ) {
        while ( rez[i].d >= rez[stiva[top]].d ) {
            sumaV -= rez[stiva[top]].v;
            top--;
        }
        top++;
        stiva[top] = i;
        sumaNec[top] = sumaV;
        sumaV += rez[i].v;

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

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

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     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%d", &rez[i].d, &rez[i].v );
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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", &q[i].s, &q[i].v );
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 4928 KB Output is correct
2 Correct 94 ms 5172 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 71 ms 4928 KB Output is correct
9 Correct 94 ms 5172 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 45 ms 2952 KB Output is correct
12 Correct 107 ms 6588 KB Output is correct
13 Correct 100 ms 5984 KB Output is correct
14 Correct 77 ms 5756 KB Output is correct
15 Correct 73 ms 5656 KB Output is correct