Cod sursa(job #2725036)

Utilizator FrostfireMagirescu Tudor Frostfire Data 18 martie 2021 12:09:10
Problema Cadrane Scor 0
Compilator cpp-64 Status done
Runda simularesimulare Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define f first
#define s second
#define NMAX 100000

using namespace std;

ifstream fin("cadrane.in");
ofstream fout("cadrane.out");

int n, sol, aib[2][NMAX+10], curr, aux[NMAX+10];
pair <int, int> v[NMAX+10];
vector <pair <int, int> > a;

int query(int poz, int t)
{	int ans = 0;
	while(poz)
		{	ans += aib[t][poz];
			int lastBit = poz & (-poz);
			poz -= lastBit;
		}
	return ans;
}

void update(int poz, int val, int t)
{	while(poz <= curr)
		{	aib[t][poz] += val;
			int lastBit = poz & (-poz);
			poz += lastBit;
		}
}

int main()
{
	fin >> n;
	for(int i=1; i<=n; i++)
		{	int x, y;
			fin >> x >> y;
			v[i].f = x;
			a.push_back({y, i});
		}
	sort(a.begin(), a.end());
	curr = 1;
	v[a[0].s].s = 1;
	for(int i=1; i<a.size(); i++)
		{	if(a[i].f != a[i-1].f)
				curr++;
			v[a[i].s].s = curr;
		}
	sort(v+1, v+n+1);
	for(int i=1; i<=n; i++)
		update(v[i].s, 1, 1);
	for(int i=1; i<=n; i++)
		aux[i] = v[i].s;
	sort(aux+1, aux+n+1);

	int p = 1, nr = n;
	for(int i=2; i<=n+1; i++)
		{	if(v[i].f != v[i-1].f)
				{	int val = i - p;
					for(int j=p; j<i; j++)
						update(v[j].s, -1, 1), nr--;
					int st = 1, dr = n - 1, ans = nr + query(aux[n], 0);
					while(st <= dr)
						{	int mij = (st + dr) / 2, val1 = query(aux[mij], 0) + nr - query(aux[mij]-1, 1);
							int val2 = query(aux[mij+1], 0) + nr - query(aux[mij+1]-1, 1);
							if(val1 <= val2) ans = val1, dr = mij - 1;
							else st = mij + 1;
						}
					sol = max(sol, ans + val);
					for(int j=p; j<i; j++)
						update(v[j].s, 1, 0);
					p = i;
				}
		}
	fout << sol << '\n';
	return 0;
}