Submission #1365922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1365922		kmath628	Fountain (eJOI20_fountain)	C++20	100 / 100	157 ms	15988 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
int nxt[17][100009], vol[17][100009], c[100009];
int main(){
    int n,q,i,j,d,r,v;
    scanf("%d %d",&n,&q);
    vector<pair<int,int> > a;
    for(i=1;i<=n;i++){
        scanf("%d %d",&d,&c[i]);
        while(!a.empty() && a.back().second<d){
            nxt[0][a.back().first]=i;
            vol[0][a.back().first]=c[i];
            a.pop_back();
        }
        a.push_back(make_pair(i,d));
    }
    for(i=1;i<=16;i++){
        for(j=1;j<=n;j++){
            nxt[i][j]=nxt[i-1][nxt[i-1][j]];
            vol[i][j]=vol[i-1][j]+vol[i-1][nxt[i-1][j]];
        }
    }
    while(q--){
        scanf("%d %d",&r,&v);
        v-=c[r];
        for(i=16;i>=0;i--){
            if(vol[i][r]<v){
                v-=vol[i][r];
                r=nxt[i][r];
            }
        }
        if(v>0) r=nxt[0][r];
        printf("%d\n",r);
    }
    return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:6:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
fountain.cpp:9:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |         scanf("%d %d",&d,&c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
fountain.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%d %d",&r,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

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