oj.uz

Submission #491161

# Submission time Handle Problem Language Result Execution time Memory
491161 2021-11-30T16:39:49 Z fuad27 Fountain (eJOI20_fountain) C++17
100 / 100
 700 ms 34432 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 4 ms 528 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 6 ms 588 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 31396 KB Output is correct
2 Correct 508 ms 29484 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 4 ms 528 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 6 ms 588 KB Output is correct
8 Correct 464 ms 31396 KB Output is correct
9 Correct 508 ms 29484 KB Output is correct
10 Correct 5 ms 572 KB Output is correct
11 Correct 254 ms 18468 KB Output is correct
12 Correct 700 ms 34432 KB Output is correct
13 Correct 597 ms 33716 KB Output is correct
14 Correct 506 ms 33024 KB Output is correct
15 Correct 454 ms 33152 KB Output is correct