oj.uz

Submission #380023

# Submission time Handle Problem Language Result Execution time Memory
380023 2021-03-20T00:31:47 Z MilosMilutinovic Fountain (eJOI20_fountain) C++14
100 / 100
 339 ms 22240 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 492 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 19712 KB Output is correct
2 Correct 237 ms 18668 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 240 ms 19712 KB Output is correct
9 Correct 237 ms 18668 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 104 ms 11904 KB Output is correct
12 Correct 339 ms 21996 KB Output is correct
13 Correct 277 ms 21776 KB Output is correct
14 Correct 194 ms 20844 KB Output is correct
15 Correct 173 ms 22240 KB Output is correct