Cod sursa(job #2725038)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 18 martie 2021 12:13:12
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda simularesimulare Marime 1.95 kb
#include <fstream>
#include <map>
#include <vector>
#include <algorithm>
#define MIN(a, b) (((a)<(b))?(a):(b))
#define MAX(a, b) (((a)>(b))?(a):(b))

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

const int N = 1e5 + 5;

int aint[4 * N], lazy[4 * N];

void propag(int node) {
	aint[node] += lazy[node];
	lazy[node*2] += lazy[node];
	lazy[node*2+1] += lazy[node];
	lazy[node] = 0;
}

void update(int node, int st, int dr, int x, int y, int val) {
	if(x<=st and dr<=y) { lazy[node] += val; return; }
	propag(node);
	int mij = (st+dr)>>1;
	if(x<=mij) update(2*node, st, mij, x, y, val);
	if(mij<y) update(2*node+1, mij + 1, dr, x, y, val);
	aint[node] = MIN(aint[2*node]+lazy[2*node], aint[2*node+1]+lazy[2*node+1]);
	lazy[node] = 0;
	//std::cout<<aint[node]<<" ";
}

int query(int node, int st, int dr, int x, int y) {
	if(x<=st and dr<=y) return aint[node]+lazy[node];
	propag(node);
	int mij = (st+dr)>>1, ans = 1000000000;
	if(x<=mij) ans = MIN(ans, query(2*node, st, mij, x, y));
	if(mij<y) ans = MIN(ans, query(2*node+1, mij+1, dr, x, y));
	return ans;
}

std::map<int, int>mx, my;
std::vector<std::pair<int, int>>v;

int main() {
	int n, X = 0, Y = 0, ans = 0;
	fin>>n;
	v.resize(n);
	for(int i=0;i<n;i++) fin>>v[i].second>>v[i].first;
	std::sort(v.begin(),v.end(), std::greater<std::pair<int, int>>());
	for(int i=0;i<n;i++) if(my.find(v[i].first)==my.end()) my[v[i].first]=++Y;
	for(int i=0;i<n;i++) std::swap(v[i].first, v[i].second);
	std::sort(v.begin(),v.end());
	for(int i=0;i<n;i++) if(mx.find(v[i].first)==mx.end()) mx[v[i].first]=++X;
	for(int i=0;i<n;i++) update(1, 1, Y, my[v[i].second], Y, 1);
	for(int i=0;i<n;i++) {
		int dr = i;
		while(dr<n and v[i].first==v[dr].first) update(1, 1, Y, my[v[dr].second], Y, -1), dr++;
		ans = MAX(ans, aint[1]+lazy[1]+dr-i);
		dr = i;
		while(dr<n and v[i].first==v[dr].first) update(1, 1, Y, 1, my[v[dr].second], 1), dr++;
		i = dr - 1;
	}
	fout<<ans;
}