Cod sursa(job #2376247)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 8 martie 2019 14:26:26
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda geometry Marime 2.11 kb
#include <algorithm>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <utility>
#include <vector>

#define x first
#define y second
using namespace std;

ifstream fi("cadrane.in");
ofstream fo("cadrane.out");

using pii = pair<int, int>;

const int N = 1e5 + 5;

struct Nod {
	int val, lazy; };

Nod pom[N * 4];
int v[N];

map<int, int> minmx;
vector<pii> pts;
int n, ql, qr, qval, bound, ant;

static void prop(int nod) {
	pom[nod].val+= pom[nod].lazy;
	pom[2 * nod].lazy+= pom[nod].lazy;
	pom[2 * nod + 1].lazy+= pom[nod].lazy;
	pom[nod].lazy = 0; }

static int eval(int nod) {
	return pom[nod].val + pom[nod].lazy; }

static int query(int nod, int st, int dr) {
	if (ql <= st && dr <= qr)
		return eval(nod);
	prop(nod);
	int mid = (st + dr) / 2, ant = 1e9;
	if (ql <= mid)
		ant = min(ant, query(2 * nod, st, mid));
	if (mid < qr)
		ant = min(ant, query(2 * nod + 1, mid + 1, dr));
	return ant; }

static void update(int nod, int st, int dr) {
	if (ql <= st && dr <= qr) {
		pom[nod].lazy+= qval;
		return; }
	prop(nod);
	int mid = (st + dr) / 2;
	if (ql <= mid)
		update(2 * nod, st, mid);
	if (mid < qr)
		update(2 * nod + 1, mid + 1, dr);

	pom[nod] = {min(eval(2 * nod), eval(2 * nod + 1)), 0}; }


static void normalize() {
	map<int, int> mp;
	int ptr = 0;
	for (auto &i: pts)
		mp[i.x] = 0;
	for (auto &i: mp)
		i.second = ++ptr;
	for (auto &i: pts)
		i.x = mp[i.x];
	mp.clear();
	ptr = 0;
	for (auto &i: pts)
		mp[i.y] = 0;
	for (auto &i: mp)
		i.second = ++ptr;
	for (auto &i: pts)
		i.y = mp[i.y]; }

int main() {
	fi >> n;
	pts.resize(n);
	for (auto &p: pts) {
		fi >> p.x >> p.y;
		p.y = -p.y; }

	normalize();
	sort(begin(pts), end(pts));
	for (auto p: pts)
		bound = max(bound, p.y);

	for (auto i: pts) {
		ql = i.y, qr = bound;
		qval = 1;
		update(1, 1, bound); }

	for (int dr = 0, st = 0; st < n; st = dr) {
		for (; dr < n && pts[st].x == pts[dr].x; ++dr) {
			ql = pts[dr].y, qr = bound;
			qval = -1;
			update(1, 1, bound); }

		ant = max(ant, eval(1) + dr - st);
		for (int i = st; i < dr; ++i) {
			ql = 1, qr = pts[i].y;
			qval = 1;
			update(1, 1, bound); } }

	fo << ant << endl;

	return 0; }