Untitled

 avatar
unknown
plain_text
24 days ago
1.4 kB
3
Indexable
#include <bits/stdc++.h>
using namespace std ;
#define For(n) for(long long i = 0; i < n; i++)
#define endl '\n'
#define int long long
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//***********************Nah I would win*************************/
void Gojo(){
    int n , sh = 0 ;cin>>n;
    vector<int> v= {0};
    map<int,int> mp;
    for(int i = 1; i <= n ; i++){
        int x , y;cin>>x >> y;
        if(!mp[x])
            v.push_back(x);
        mp[x] += y;
    }
    sort(v.begin() , v.end());
    int shots = 0;
    priority_queue<int,vector<int>> pq;
    for(int i = 1; i < v.size() ; i++){
        sh += v[i] - v[i-1];
        // cout << sh <<' '<< shots<<  endl;
        if(pq.empty()){
            if(sh >= mp[v[i]]){
                sh -= mp[v[i]];
                pq.push(mp[v[i]]);
            }                
            else
                shots++;
            continue;    
        }
        if(sh >= mp[v[i]]){
            sh -= mp[v[i]];
            pq.push(mp[v[i]]);
        }                
        else{
            shots++;
            if(mp[v[i]] < pq.top()){
                sh += pq.top() - mp[v[i]];
                pq.pop();
            }
        }    
    }
    cout << shots;
}

signed main()
{
    fast   
    int Tt =1;
    // cin>>Tt;
    while (Tt--){
        Gojo();
        cout << endl;
    }    
}
Editor is loading...
Leave a Comment