Submission #895690

#	Time	Username	Problem	Language	Result	Execution time	Memory
895690		vjudge1	Fountain (eJOI20_fountain)	C++17	30 / 100	99 ms	19876 KiB

fountain

#include<bits/stdc++.h>
using namespace std;
int const maxn=1e5+5;
int st[maxn][20],sum[maxn][20],d[maxn];
int s[maxn],top;
int main(){
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d%d",d+i,&sum[i][0]);
        while(top&&d[s[top]]<=d[i])st[s[top--]][0]=i;
        s[++top]=i;
    }
    for(int j=1;j<=19;j++){
        for(int i=1;i<=n;i++){
            st[i][j]=st[st[i][j-1]][j-1];
            sum[i][j]=sum[i][j-1]+sum[st[i][j-1]][j-1];
        }
    }
    int p,v;
    while(q--){
        scanf("%d%d",&p,&v);
        for(int i=19;~i;i--){
            if(v>sum[p][i])v-=sum[p][i],p=st[p][i];
        }
        printf("%d\n",p);
    }
}

Compilation message (stderr)

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

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