oj.uz

Submission #412799

# Submission time Handle Problem Language Result Execution time Memory
412799 2021-05-27T14:37:01 Z LucaIlie Fountain (eJOI20_fountain) C
100 / 100
 136 ms 10660 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() {
    //FILE *fin, *fout;
    int n, m, top, st, dr, mij, i, j;
    long long sumaV;

    //fin = fopen( "fountain.in", "r" );
    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;
    }
    //fclose( fin );

    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];
        }
    }

    //fout = fopen( "fountain.out", "w" );
    for ( i = 1; i <= m; i++ )
        printf( "%d\n", q[i].rasp );
    //fclose( fout );

    return 0;
}

Compilation message

fountain.c: In function 'main':
fountain.c:27:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf( "%d%d", &n, &m );
      |     ^~~~~~~~~~~~~~~~~~~~~~~
fountain.c:31:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf( "%d%d", &rez[i].d, &rez[i].v );
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.c:33:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf( "%d%d", &q[i].s, &q[i].v );
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 7800 KB Output is correct
2 Correct 97 ms 8260 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 86 ms 7800 KB Output is correct
9 Correct 97 ms 8260 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 60 ms 4672 KB Output is correct
12 Correct 136 ms 10660 KB Output is correct
13 Correct 119 ms 9540 KB Output is correct
14 Correct 96 ms 8692 KB Output is correct
15 Correct 106 ms 8948 KB Output is correct