제출 #835087

#제출 시각아이디문제언어결과실행 시간메모리
835087jasminAdvertisement 2 (JOI23_ho_t2)C++17
10 / 100
163 ms25692 KiB
//JOI 2023 Final Round #include<bits/stdc++.h> using namespace std; #define int long long const int INF=1e18; void solve(){ int n; cin >> n; vector<pair<int,int> > a(n); for(int i=0; i<n; i++){ cin >> a[i].second >> a[i].first; } sort(a.begin(), a.end()); reverse(a.begin(), a.end()); set<pair<int,int> > given; int ans=0; for(int i=0; i<n; i++){ auto [e, x]=a[i]; auto r=given.upper_bound({x, e}); if(r!=given.end()){ auto [x2, e2]=*r; if(e2-e >= x2-x) continue; } if(r!=given.begin()){ auto [x2, e2] =*prev(r); if(e2-e >= x-x2) continue; } ans++; given.insert({x, e}); } cout << ans << "\n"; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<pair<int,int> > a(n); vector<pair<int,int> > sorted(n); for(int i=0; i<n; i++){ cin >> a[i].first >> a[i].second; sorted[i]={a[i].second-a[i].first, i}; } sort(sorted.begin(), sorted.end()); reverse(sorted.begin(), sorted.end()); int maxi=-INF; int ans=0; for(auto [val, i]: sorted){ auto [x, e] = a[i]; if(x+e <= maxi) continue; maxi = x+e; ans++; } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...