제출 #975295

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

fountain

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 5;
const ll LOG = 61;
#define vll vector <ll>
#define pll pair <ll, ll>
#define fi first
#define se second
#define endl '\n'

ll n, m;
pll a [MAXN];
vector <vector <pll> > b (MAXN);
vector <array <ll, 3> > v;
ll ans [MAXN];

ll lb(ll x){
    ll l = 1, r = v.size()-1, ret = 0;
    while(l <= r){
        ll mid = (l+r)/2;
        if(v.back()[1] - v[mid-1][1] >= x){
            ret = v[mid][2];
            l = mid + 1;
        }
        else{
            r = mid - 1;
        }
    }
    return ret;
}

void solve(){
    cin >> n >> m;
    for(ll i = 1; i <= n; i++){
        cin >> a[i].fi >> a[i].se;
    }
    for(ll i = 1; i <= m; i++){
        ll x, y; cin >> x >> y;
        b[x].push_back({y, i});
    }
    v.push_back({INF, 0, 0});
    for(ll i = n; i >= 1; i--){
        while(!v.empty()){
            if(v.back()[0] > a[i].fi) break;
            v.pop_back();
        }
        if(!v.empty()) a[i].se += v.back()[1];
        v.push_back({a[i].fi, a[i].se, i});
        // for(auto x : v){
        //     cout << x[0] << " " << x[1] << " " << x[2] << endl;
        // }cout << endl;
        for(auto x : b[i]){
            ans[x.se] = lb(x.fi);
            // cout << x.fi << " << " << lb(x.fi) << endl;
        }
    }
    for(ll i = 1; i <= m; i++){
        cout << ans[i] << endl;
    }cout << endl;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // ll t; cin >> t;
    // while(t--){
        solve();
    // }
}

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