Submission #412799

#	Time	Username	Problem	Language	Result	Execution time	Memory
412799		LucaIlie	Fountain (eJOI20_fountain)	C11	100 / 100	136 ms	10660 KiB

fountain

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40