oj.uz

답안 #825476

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
825476 2023-08-14T22:27:56 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 516 ms 37672 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define in insert
#define ld long double
#define ll long long
#define pii pair<ll,ll>
#define vl vector<ll>
#define mpr make_pair
#define F first
#define S second
#define lg(a) __lg(a)
#define all(v) v.begin(),v.end()
//#define endl "\n"
#define inf 0x3F3F3F3F
using namespace std;
const int mod = 1e9+7;
const int sz = 1e5+5;
const ll oo = 1000000000000000005;
ll st[20][sz], water[20][sz];
void solve(){
    ll n,q,i,j,len;
    cin>>n>>q;
    deque<pair<ll,ll>> dq;
    for(i=1;i<=n;i++){
        cin>>len>>water[0][i];
        while(!dq.empty() && len > dq.front().first){
            st[0][dq.front().second]=i;
            dq.pop_front();
        }
        dq.push_front({len,i});
    }
    for(i=1;i<20;i++){
        for(j=1;j<=n;j++){
            st[i][j] = st[i-1][st[i-1][j]];
            water[i][j] = water[i-1][j] + water[i-1][st[i-1][j]];
        }
    }
    while(q--){
        ll ix, g;
        cin>>ix>>g;
        for(i=19;i>=0;i--){
            if(water[i][ix] < g){
                g-=water[i][ix];
                ix = st[i][ix];
            }
        }
        cout << ix << endl;
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t=1;
    //cin>>t;
    while(t--){
        solve();
    }

}
/*
2 1
1 2 5
4
2
1 2
*/

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 5 ms 888 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 301 ms 33884 KB Output is correct
2 Correct 345 ms 31812 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 5 ms 888 KB Output is correct
8 Correct 301 ms 33884 KB Output is correct
9 Correct 345 ms 31812 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 147 ms 20132 KB Output is correct
12 Correct 516 ms 36956 KB Output is correct
13 Correct 423 ms 36524 KB Output is correct
14 Correct 312 ms 35668 KB Output is correct
15 Correct 291 ms 37672 KB Output is correct