oj.uz

Submission #835135

# Submission time Handle Problem Language Result Execution time Memory
835135 2023-08-23T08:57:10 Z TsotneSV Fountain (eJOI20_fountain) C++17
0 / 100
 186 ms 32304 KB 
#include <bits/stdc++.h>
using namespace std;
/* /\_/\
  (= ._.)
  / >  \>
*/
//#define int long long
 
#define fi first
#define se second
#define pb push_back
#define ins insert
#define mp make_pair
#define endl "\n"
#define sz(x) (int) (x).size()
#define deb(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<" "<<x<<endl
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
 
const ll mod=1e9+7;
const ll MOD=998244353;
const ll INF=1e17;
const int MAXN=1e5+5;
 
int n,q,nxt[MAXN];
ll d[MAXN],c[MAXN];
pll jump[17][MAXN];
 
void solve(){
    cin>>n>>q; 
    for(int i=0;i<n;i++) {
        cin>>d[i]>>c[i];    
        nxt[i] = -1;
    }
 
    stack<pll> s; s.push({d[n-1],n-1});
 
    for(int i=n-2;i>=0;i--) {
 
        while(s.size() && s.top().fi <= d[i]) {
            s.pop();
        }
        if(s.size()) nxt[i] = s.top().se;
        s.push({d[i],i});
    }
 
    for(int i=0;i<17;i++) {
        for(int j=n-1;j>=0;j--) {
            if(i == 0) {
                jump[i][j].fi = nxt[j];
                jump[i][j].se = (c[j] + (nxt[j] == -1 ? 0 : c[nxt[j]]));
            }
            else {
                jump[i][j].fi = jump[i-1][jump[i-1][j].fi].fi;
                jump[i][j].se = jump[i-1][jump[i-1][j].fi].se + c[j]; 
            }
        }
    }
 
    while(q--) {
        int u; ll v;
        cin>>u>>v; u--; 
        int l=1,r=n,ret=-1;
        
        if(c[u] >= v) {
            deb(u + 1);
            continue;
        }
 
        while(l<=r) {
            int mid = (l + r)/2,tm = mid;
 
            int node = u,cnt = 0; ll sum = 0;
 
            while(tm) {
                if(tm&1) {
                    sum += jump[cnt][node].se;
                    node = jump[cnt][node].fi;
                    if(node == -1) break;
                } tm/=2; cnt++;
            }
 
            if(sum < v && node == -1) {
                ret = -1;
                break;
            }
 
            if(sum < v) {
                l = mid + 1;
            }else if(sum >= v){
                ret = node;
                r = mid - 1;
            }
 
        } deb(ret + 1);
 
 
    }
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int tt=1;
  //  cin>>tt;
    while(tt--){
        solve();
    }
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 186 ms 32304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -