Submission #1274033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274033		rana_azka	Fountain (eJOI20_fountain)	C++20	100 / 100	240 ms	20692 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e18;
const int MOD = 1e9+7;
const int MAXN = 2e5;

int n, m;
int diameter[MAXN+5];
int kapasitas[MAXN+5];
int ans[MAXN+5];
vector<tuple<int, int, int>> query;         // {tap, vol, idx}
vector<pair<int, int>> query_idx[MAXN+5];   // {val, idx}
vector<tuple<int, int, int>> monotonic;     // {diameter, pref, idx}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> diameter[i] >> kapasitas[i];
    for(int i = 1; i <= m; i++){
        int tap, vol; cin >> tap >> vol;
        query.push_back({tap, vol, i});
        query_idx[tap].push_back({vol, i});
    }
    
    sort(query.begin(), query.end());
    
    monotonic.push_back({INF, 0, 0});
    for(int i = n; i >= 1; i--){
        auto [dmtr, pref, idx] = monotonic.back();
        while(!monotonic.empty() && diameter[i] >= dmtr){
            monotonic.pop_back();
            dmtr = get<0>(monotonic.back());
            pref = get<1>(monotonic.back());
            idx = get<2>(monotonic.back());
        }
        
        monotonic.push_back({diameter[i], pref + kapasitas[i], i});
        
        auto [cur_dmtr, cur_pref, cur_idx] = monotonic.back();
        for(auto [vol, idx] : query_idx[i]){
            int res = 0;
            int left = 1, right = monotonic.size() - 1;
            int mid;
            while(left <= right){
                mid = (left + right) / 2;
                auto [next_dmtr, next_pref, next_idx] = monotonic[mid-1];
                auto [res_dmtr, res_pref, res_idx] = monotonic[mid];

                int cek = cur_pref - next_pref;
                if(cek >= vol){
                    res = res_idx;
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }

            ans[idx] = res;
        }
    }

    for(int i = 1; i <= m; i++) cout << ans[i] << endl;

}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    while(tc--){
        solve();
    }


    return 0;
}

/*
TEST CASE

6 5 
4 10 
6 8 
3 5 
4 14 
10 9 
4 20  
1 25 
6 30 
5 8 
3 13 
2 8
*/

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