# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1105094 |
2024-10-25T10:43:34 Z |
Faggi |
Sails (IOI07_sails) |
C++11 |
|
216 ms |
9228 KB |
#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]}); } } 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){ ll ma, sob, i, res=0ll; for(i=tam; i>0ll; i--) { ma=min(x,tamDP[i]); sob=0ll; if(dp[i]>ma) { sob=dp[i]-ma; dp[i]=ma; dp[i-1ll]+=sob; } } for(i=tam; i>0ll; i--) { res+=calcs[dp[i]]; } return res;}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;}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Incorrect |
0 ms |
336 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
592 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
42 ms |
2344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
46 ms |
2832 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
84 ms |
4272 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
216 ms |
9228 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
180 ms |
9044 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
200 ms |
8248 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |