Pagini recente » Cod sursa (job #660078) | Cod sursa (job #3031263) | Cod sursa (job #1502362) | Cod sursa (job #2528712) | Cod sursa (job #757620)
Cod sursa(job #757620)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
int N;
pair<int, int> A[100002];
int pos[100002];
int S[100002];
int result;
int MARB[4 * 100002], ARB[4 * 100002], Ap1, Ap2, Av;
void Aupdate(int nod, int s1, int s2)
{
if (Ap1 <= s1 && s2 <= Ap2)
{
ARB[nod] += (s2 - s1 + 1) * Av;
MARB[nod] += Av;
return;
}
int mid = (s1 + s2) >> 1;
if (ARB[nod] != ARB[nod * 2] + ARB[nod * 2 + 1])
{
int remain = (ARB[nod] - (ARB[nod * 2] + ARB[nod * 2 + 1])) / (s2 - s1 + 1);
ARB[nod * 2] += remain * (mid - s1 + 1);
ARB[nod * 2 + 1] += remain * (s2 - mid);
MARB[nod * 2] += remain;
MARB[nod * 2 + 1] += remain;
}
if (Ap1 <= mid) Aupdate(nod * 2, s1, mid);
if (Ap2 > mid) Aupdate(nod * 2 + 1, mid + 1, s2);
ARB[nod] = ARB[nod * 2] + ARB[nod * 2 + 1];
MARB[nod] = min(MARB[nod * 2], MARB[nod * 2 + 1]);
}
class compareB
{
public:
inline bool operator () (const int& p1, const int& p2)
{
return A[p1].second < A[p2].second;
}
};
int main()
{
ifstream fin("cadrane.in");
ofstream fout("cadrane.out");
fin >> N;
for (int i = 1; i <= N; ++i)
fin >> A[i].first >> A[i].second;
sort(A + 1, A + N + 1);
for (int i = 1; i <= N; ++i)
pos[i] = i;
sort(pos + 1, pos + N + 1, compareB());
int now = 0;
for (int i = 1; i <= N; ++i)
{
++now;
while (i + 1 <= N && A[pos[i]].second == A[pos[i + 1]].second)
{
A[pos[i]].second = now;
++i;
}
A[pos[i]].second = now;
}
for (int i = 1; i <= N; ++i)
++S[A[i].second];
for (int i = 1; i <= N; ++i)
S[i] += S[i - 1];
for (int i = 1; i <= N; ++i)
{
Ap1 = Ap2 = i;
Av = S[i];
Aupdate(1, 1, N);
}
int wh = 1;
for (int i = 1; i <= N; ++i) // baleez
{
while (A[wh].first < A[i].first)
{
Ap1 = A[wh].second, Ap2 = N, Av = -1;
Aupdate(1, 1, N);
++wh;
}
while (i + 1 <= N && A[i].first == A[i + 1].first)
{
Ap1 = 1, Ap2 = A[i].second, Av = 1;
Aupdate(1, 1, N);
++i;
}
Ap1 = 1, Ap2 = A[i].second, Av = 1;
Aupdate(1, 1, N);
result = max(result, MARB[1]);
}
fout << result << '\n';
fin.close();
fout.close();
}