oj.uz

답안 #689454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
689454 2023-01-28T14:01:45 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 674 ms 34372 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 7 ms 596 KB Output is correct
7 Correct 4 ms 580 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 439 ms 31544 KB Output is correct
2 Correct 516 ms 29572 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 7 ms 596 KB Output is correct
7 Correct 4 ms 580 KB Output is correct
8 Correct 439 ms 31544 KB Output is correct
9 Correct 516 ms 29572 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 261 ms 18448 KB Output is correct
12 Correct 674 ms 34372 KB Output is correct
13 Correct 557 ms 33684 KB Output is correct
14 Correct 484 ms 32936 KB Output is correct
15 Correct 455 ms 33252 KB Output is correct