Untitled
unknown
plain_text
10 months ago
1.4 kB
6
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