Submission #380023

#	Time	Username	Problem	Language	Result	Execution time	Memory
380023		MilosMilutinovic	Fountain (eJOI20_fountain)	C++14	100 / 100	339 ms	22240 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int N=100050;
const int LOG=20;
int d[N],c[N],go[N][LOG],sum[N][LOG];
int main(){
    int n,q;scanf("%i%i",&n,&q);
    for(int i=1;i<=n;i++)scanf("%i%i",&d[i],&c[i]);
    priority_queue<pii> pq;
    for(int i=1;i<=n;i++){
        while(!pq.empty()&&-pq.top().first<d[i])go[pq.top().second][0]=i,pq.pop();
        pq.push({-d[i],i});
    }
    while(!pq.empty())go[pq.top().second][0]=0,pq.pop();
    for(int i=1;i<=n;i++)sum[i][0]=c[i];
    go[0][0]=sum[0][0]=0;
    for(int j=1;j<LOG;j++){
        for(int i=0;i<=n;i++){
            go[i][j]=go[go[i][j-1]][j-1];
            sum[i][j]=sum[i][j-1]+sum[go[i][j-1]][j-1];
        }
    }
    while(q--){
        int a,b;scanf("%i%i",&a,&b);
        for(int j=LOG-1;j>=0;j--){
            if(sum[a][j]>=b)continue;
            b-=sum[a][j],a=go[a][j];
        }
        printf("%i\n",a);
    }
    return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:8:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 |     int n,q;scanf("%i%i",&n,&q);
      |             ~~~~~^~~~~~~~~~~~~~
fountain.cpp:9:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 |     for(int i=1;i<=n;i++)scanf("%i%i",&d[i],&c[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~
fountain.cpp:25:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |         int a,b;scanf("%i%i",&a,&b);
      |                 ~~~~~^~~~~~~~~~~~~~

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