oj.uz

Submission #485887

# Submission time Handle Problem Language Result Execution time Memory
485887 2021-11-09T15:48:23 Z gavgav Fountain (eJOI20_fountain) C++17
100 / 100
 107 ms 9540 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 n, m, top, st, dr, mij, i, j;
    long long sumaV;
    scanf( "%d%d", &n, &m );
    rez[0].d = MAX_D + 1;
    rez[0].v = 0;
    for ( i = 1; i <= n; i++ )
        scanf( "%d%d", &rez[i].d, &rez[i].v );
    for ( i = 1; i <= m; 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 = n; 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 <= m; 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", &n, &m );
      |     ~~~~~^~~~~~~~~~~~~~~~~~
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 1 ms 332 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 300 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 4804 KB Output is correct
2 Correct 80 ms 8132 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 1 ms 332 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 300 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 4804 KB Output is correct
9 Correct 80 ms 8132 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 45 ms 4672 KB Output is correct
12 Correct 107 ms 9540 KB Output is correct
13 Correct 93 ms 8836 KB Output is correct
14 Correct 81 ms 8688 KB Output is correct
15 Correct 73 ms 8636 KB Output is correct