Submission #1200484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200484		badge881	Fountain (eJOI20_fountain)	C++20	100 / 100	130 ms	16460 KiB

fountain

#include <bits/stdc++.h>
using namespace std;

const int LOGK = 17, MAXN = 1e5 + 7;

int jump[MAXN][LOGK];
int suma[MAXN][LOGK];


int main(){
    int n, q;
    scanf("%d%d", &n, &q);
    int a, b;

    vector<pair<int, int>> tab;

    for (int i = 0; i < n; i++){
        scanf("%d%d", &a, &b);
        tab.push_back({a, b});
    }
    tab.push_back({2e9, 2e9});

    vector<int> stos;
    stos.push_back(n);

    for (int i = n - 1; i >= 0; i--){
        while (tab[stos.back()].first <= tab[i].first) 
            stos.pop_back();
        jump[i][0] = stos.back();
        suma[i][0] = tab[stos.back()].second;
        stos.push_back(i);
    }

    jump[n][0] = n;

    for (int k = 1; k < LOGK; k++){
        for (int v = 0; v <= n; v++){
            jump[v][k] = jump[jump[v][k - 1]][k - 1];
            if (jump[v][k] == n) 
                suma[v][k] = 2e9;
            else 
                suma[v][k] = suma[v][k - 1] + suma[jump[v][k - 1]][k - 1];
        }
    }


    while (q--){
        scanf("%d%d", &a, &b);
        a--;

        int aktsuma = tab[a].second;

        for (int k = LOGK - 1; k >= 0; k--){
            if (jump[a][k] == n) continue;
            if (aktsuma + suma[a][k] < b){
                aktsuma += suma[a][k];
                a = jump[a][k];
            }
        }

        if (aktsuma < b) 
            a = jump[a][0];
        if (a == n) 
            a = -1;

        printf("%d\n", a + 1);
    }


    return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
fountain.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~
fountain.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~

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