// M
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct CHT
{
typedef pair < ll , ll > Line;
vector < pair < ll , Line > > A;
vector < vector < pair < ll , Line > > > U;
ll INF = 1e18;
inline void Add(Line X)
{
vector < pair < ll , Line > > nwu;
while (A.size() && Intersection(A.back().second, X) <= A.back().first)
nwu.push_back(A.back()), A.pop_back();
if (A.size())
A.push_back({Intersection(A.back().second, X), X});
else
A.push_back({-INF, X});
U.push_back(nwu);
}
inline ll GetMax(ll X)
{
int lb = upper_bound(A.begin(), A.end(), pair < ll , Line > {X, {INF, INF}}) - A.begin() - 1;
return (A[lb].second.first * X + A[lb].second.second);
}
inline ll Intersection(Line X, Line Y)
{
if (X.first == Y.first)
return X.second <= Y.second ? -INF : INF;
return ((X.second - Y.second) / (Y.first - X.first)) + ((X.second - Y.second) % (Y.first - X.first) > 0);
}
inline void Undo()
{
assert(A.size() && U.size());
vector < pair < ll , Line > > nwu = U.back();
U.pop_back(); A.pop_back();
while (nwu.size())
A.push_back(nwu.back()), nwu.pop_back();
}
};
const int N = 100005;
int n, H[N], K[N], C[N];
ll PS[N];
CHT Cht;
/*inline bool Solve(int md)
{
memset(C, 0, sizeof(C));
for (int i = 1; i <= n; i ++)
C[H[i] - K[i] + 1] ++, C[H[i] + 1] --;
for (int i = 1; i < N; i ++)
C[i] += C[i - 1];
ll LeftOver = 0;
for (int i = N - 1; i; i --)
{
int tmp = min(LeftOver, (ll)md - C[i]);
LeftOver -= tmp;
C[i] += tmp;
assert(C[i] <= md);
}
return !LeftOver;
}*/
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++)
scanf("%d%d", &H[i], &K[i]);
for (int i = 1; i <= n; i ++)
C[H[i] - K[i] + 1] ++, C[H[i] + 1] --;
for (int i = 1; i < N; i ++)
C[i] += C[i - 1];
for (int i = 1; i < N; i ++)
PS[i] = PS[i - 1] + C[i];
for (int i = N - 1; i; i --)
Cht.Add({-i, PS[i]});
for (int i = 1; i + 1 < N; i ++)
{
int le = max(C[i], 0) - 1, ri = n, md;
while (ri - le > 1)
{
md = (le + ri) >> 1;
if (Cht.GetMax(md) <= PS[i - 1] - (ll)md * (i - 1))
ri = md;
else
le = md;
}
PS[i] += ri - C[i];
C[i + 1] -= ri - C[i];
C[i] = ri;
Cht.Undo();
}
/* LOL, this was pure nonsense and it got 90 points! XD
int le = 0, ri = N, md;
while (ri - le > 1)
{
md = (le + ri) >> 1;
if (Solve(md))
ri = md;
else
le = md;
}
// How to do it with ri you ask? I don't know either ...
Solve(ri);
int ptr = 1;
for (int i = N - 1; i; i --)
if (C[i] == ri)
{
while (ptr < i && C[ptr] == ri)
ptr ++;
if (ptr >= i)
break;
C[i] --;
C[ptr] ++;
}
vector < int > A;
for (int i = 1; i < N; i ++)
{
vector < int > Tbo = {C[i]};
while (Tbo.size())
{
if (!A.size() || A.back() >= Tbo.back())
{
A.push_back(Tbo.back());
Tbo.pop_back();
continue;
}
int nd = (Tbo.back() - A.back() + 1) / 2;
Tbo.back() -= nd;
Tbo.push_back(A.back() + nd);
A.pop_back();
}
}
assert((int)A.size() == N - 1);
for (int i = 1; i < N; i ++)
C[i] = A[i - 1];*/
/*for (int i = 1; i < N; i ++)
assert(C[i] <= ri);
bool Fail = 1;
for (int i = 1; i < N; i ++)
if (C[i] == ri)
Fail = 0;
assert(!Fail);*/
for (int i = 2; i < N; i ++)
assert(C[i - 1] >= C[i]);
ll tot = 0;
for (int i = 1; i < N; i ++)
tot += (ll)C[i] * (C[i] - 1) / 2;
printf("%lld\n", tot);
return 0;
}
Compilation message
sails.cpp: In function 'int main()':
sails.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
65 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
sails.cpp:67:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
67 | scanf("%d%d", &H[i], &K[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
6960 KB |
Output is correct |
| 2 |
Correct |
22 ms |
6960 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
6992 KB |
Output is correct |
| 2 |
Correct |
24 ms |
6960 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
6960 KB |
Output is correct |
| 2 |
Correct |
23 ms |
6960 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
25 ms |
6960 KB |
Output is correct |
| 2 |
Correct |
26 ms |
6960 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
31 ms |
7092 KB |
Output is correct |
| 2 |
Correct |
37 ms |
6960 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
46 ms |
7088 KB |
Output is correct |
| 2 |
Correct |
50 ms |
7592 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
48 ms |
8112 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
72 ms |
7984 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
102 ms |
8548 KB |
Output is correct |
| 2 |
Correct |
78 ms |
8872 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
101 ms |
8404 KB |
Output is correct |
| 2 |
Correct |
52 ms |
8368 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
121 ms |
8920 KB |
Output is correct |
| 2 |
Correct |
56 ms |
8744 KB |
Output is correct |
