#include <bits/stdc++.h>
#define ll long long
using namespace std;vector<ll>tamDP;vector<ll>calcs;ll tam;bool can(vector<ll> dp,ll x){ ll ma, sob=0, i,pos,posR; priority_queue<pair<ll,ll>>sum,res; for(i=tam; i>0ll; i--) { ma=min(x,tamDP[i]); if(dp[i]>ma) { sob=dp[i]-ma; dp[i]=ma; if(i>1ll) sum.push({i,sob}); else return 0; } else { res.push({i,ma-dp[i]}); } } sob=0; while(sum.size()&&res.size()) { pos=sum.top().first; sob+=sum.top().second; sum.pop(); while(res.size()&&res.top().first>pos) res.pop(); while(res.size()&&sob>0) { sob-=res.top().second; posR=res.top().first; res.pop(); } if(sob>0) return 0; else { res.push({posR,abs(sob)}); sob=0; } } if(sum.size()||sob>0) return 0; return 1;}ll calc(vector<ll> dp, ll x){ priority_queue<pair<ll,ll>>pq; ll rest, a, b, i; for(i=tam; i>0; i--) { if(dp[i]<min(x,tamDP[i])) { pq.push({i,min(x,tamDP[i])-dp[i]}); } } for(i=tam; i>0; i--) { while(pq.size()&&pq.top().first>i) pq.pop(); if(dp[i]>min(x,tamDP[i])) { while(dp[i]>min(x,tamDP[i])) { rest=min(dp[i]-min(x,tamDP[i]),pq.top().second); dp[i]-=rest; dp[pq.top().first]+=rest; if(pq.top().second-rest>0) { a=pq.top().first; b=pq.top().second-rest; pq.pop(); pq.push({a,b}); } else { pq.pop(); } } } } ll ret=0; for(i=tam; i>0; i--) { ret+=calcs[dp[i]]; } return ret;}int main(){ ll n, i, mi=0ll, ma=0ll, piv,pos; cin >> n; calcs.resize(n+1ll); calcs[0ll]=0ll; calcs[1ll]=0ll; for(i=2ll; i<=n; i++) { calcs[i]+=calcs[i-1ll]+(i-1ll); } vector<pair<ll,ll>>v(n); for(i=0ll; i<n; i++) { cin >> v[i].first >> v[i].second; tam=max(v[i].first,tam); } vector<ll> dp(tam+1,0ll); tamDP.resize(tam+1,0ll); for(i=0ll; i<n; i++) { dp[v[i].first]+=1ll; dp[v[i].first-v[i].second]-=1ll; tamDP[v[i].first]+=1ll; } ma=dp[tam]; for(i=tam-1ll; i>=0ll; i--) { dp[i]+=dp[i+1ll]; ma=max(ma,dp[i]); tamDP[i]+=tamDP[i+1ll]; } pos=ma; while(mi<=ma) { piv=(mi+ma)/2ll; if(can(dp,piv)) { ma=piv-1ll; pos=piv; } else { mi=piv+1ll; } } cout << calc(dp,pos) << endl; return 0;}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
504 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
504 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
44 ms |
2368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
46 ms |
2860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
88 ms |
4784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
225 ms |
9232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
183 ms |
9516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
203 ms |
8252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
