제출 #976039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
976039		vjudge1	Fountain (eJOI20_fountain)	C++17	100 / 100	353 ms	39784 KiB

fountain

#include <bits/stdc++.h>
using namespace std; 
#define int long long 
#define fi first 
#define se second 
#define pb push_back
pair<int,int>a[100005]; 
vector<pair<int,int>>que[100005]; 
vector<int>adj[100005]; 
int ans[200005]; 
vector<int>nodes; 
vector<int>pref; 
int n, q; 
void dfs(int node){
    //cout << "here >> " << node << endl; 
    nodes.pb(node); 
    if(node == n + 1)pref.pb(0); 
    else pref.pb(pref.back() + a[node].se); 
    for(auto it : que[node]){
        int l = 1, r = pref.size() - 1, ret = -1;
        while(l <= r){
            int mid = (l+r)/2; 
            if(pref[pref.size()-1] - pref[mid-1] >= it.fi){
                ret = mid; 
                l = mid + 1; 
            }
            else{
                r = mid - 1; 
            }
        }
        //cout << "here1 >> " << it.fi << " " << ret << endl; 
        if(ret == -1)ans[it.se] = 0; 
        else ans[it.se] = nodes[ret]; 
    }
    for(auto it : adj[node])dfs(it); 
    pref.pop_back(); 
    nodes.pop_back(); 
}
signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cin >> n >> q; 
    for(int i = 1; i <= n; i++){
        cin >> a[i].fi >> a[i].se; 
    }
    for(int i = 1; i <= q; i++){
        int x,y; cin >> x >> y; 
        que[x].pb({y,i}); 
    }
    vector<pair<int,int>>v; 
    for(int i = 1; i <= n; i++){
        v.push_back({a[i].fi,i}); 
    }
    sort(v.begin(),v.end(),greater<pair<int,int>>()); 
    set<int>s; 
    s.insert(n+1); 
    vector<int>tmp; 
    for(int i = 0; i < n; i++){
        int node = v[i].se; 
        int idx = *s.upper_bound(node); 
        adj[idx].pb(node); 
        tmp.pb(node); 
        if(i == n - 1 || v[i].fi != v[i+1].fi){
            for(auto it : tmp)s.insert(it); 
            tmp.clear(); 
        }
    }
    dfs(n+1); 
    for(int i = 1; i <= q; i++){
        cout << ans[i] << endl; 
    }
}

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