Submission #491161

#	Time	Username	Problem	Language	Result	Execution time	Memory
491161		fuad27	Fountain (eJOI20_fountain)	C++17	100 / 100	700 ms	34432 KiB

fountain

#include<bits/stdc++.h>
using namespace std;
const int LOG = 18;
const int MAXN = 1e5 + 5;
stack<int> s;
long long up[MAXN][LOG];
long long sum[MAXN][LOG];
int n, q;
int main () {
    cin >> n >> q;
    int d[n+1], c[n+1];
    for(int i = 0;i<n;i++) {
        cin >> d[i] >> sum[i][0];
    }
    d[n] = 1e9 + 10;
    sum[n][0] = 1e9 + 10; 
    up[n][0] = n;
    s.push(n);
    for(int i = n-1;i>=0;i--) {
        while(d[s.top()]<=d[i])s.pop();
        up[i][0] = s.top();
        s.push(i);
    }
    for(int i = 1;i<LOG;i++) {
        for(int j = 0;j<n;j++) {
            up[j][i] = up[up[j][i-1]][i-1];
            sum[j][i] = sum[up[j][i-1]][i-1]+sum[j][i-1];
        }
    }
        long long r, l;
  
    while(q--) {
        cin >> r >> l;
        r--;
        for(int i=LOG-1;i>=0;i--) {
            if(l > sum[r][i]){
                l-=sum[r][i];
                r=up[r][i];
            }
        }
        if(r == n)cout << 0 << endl;
        else 
            cout << r+1 << endl;
    }
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:11:17: warning: unused variable 'c' [-Wunused-variable]
   11 |     int d[n+1], c[n+1];
      |                 ^

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