Submission #106808

#	Time	Username	Problem	Language	Result	Execution time	Memory
106808		polyfish	New Home (APIO18_new_home)	C++14	0 / 100	5103 ms	93060 KiB

new_home

//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 300002;
const int INF = 1e9+100;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct treap {

	struct item {
		int L, R, max_r, prior;
		item *l, *r;

		item(int L=0, int R=0): L(L), R(R) {
			max_r = R;
			//prior = uniform_int_distribution<int>(1, INF)(rng);
			prior = 1;
            l = r = nullptr;
		}
	};

	typedef item * pitem;

	pitem root = nullptr;

	int get_max_r(pitem t) {
		return t ? t->max_r : 0;
	}

	void upd(pitem t) {
		if (t)
			t->max_r = max(t->R, max(get_max_r(t->l), get_max_r(t->r)));
	}

	void split(pitem t, pitem &l, pitem &r, int key) {
		if (!t) {
			l = r = nullptr;
		}
		else {
			if (key>t->L)
				split(t->r, t->r, r, key), l = t;
			else
				split(t->l, l, t->l, key), r = t;
		}

		upd(t);
	}

	void merge(pitem &t, pitem l, pitem r) {
		if (!l || !r) {
			t = l ? l : r;
		}
		else {
			if (l->prior>r->prior)
				merge(l->r, l->r, r), t = l;
			else
				merge(r->l, l, r->l), t = r;
		}

		upd(t);
	}

	void insert(pitem &t, pitem it) {
		if (!t) {
			t = it;
		}
		else {
			if (it->prior>t->prior)
				split(t, it->l, it->r, it->L), t = it;
			else
				insert(it->L<t->L ? t->l : t->r, it);
		}

		upd(t);
	}

	void erase(pitem &t, int L, int R) {
		if (!t)
			return;

		if (t->L==L && t->R==R)
			merge(t, t->l, t->r);
		else
			erase(L<t->L ? t->l : t->r, L, R);

		upd(t);
	}

	int get(pitem t, int L) {
		if (!t)
			return -INF;

		if (L<t->L)
			return get(t->l, L);

		return max(max(t->R, get_max_r(t->l)), get(t->r, L));
	}

	void insert(int L, int R) {
		insert(root, new item(L, R));
	}

	void erase(int L, int R) {
		erase(root, L, R);
	}

	int get(int L) {
		return get(root, L);
	}
};

struct store {
	int x, t, a, b;
};

struct query {
	int l, y;
};

int n, k, nQueries, res[MAX_N];
vector<int> T, store_event[MAX_N*2], q[MAX_N*2];
store s[MAX_N];
query Q[MAX_N];
map<int, int> pos[MAX_N*2];
treap interval_set;

void read_input() {
	cin >> n >> k >> nQueries;

	for (int i=1; i<=n; ++i)
		cin >> s[i].x >> s[i].t >> s[i].a >> s[i].b;

	for (int i=1; i<=nQueries; ++i) {
		cin >> Q[i].l >> Q[i].y;
	}
}

void compress() {
	for (int i=1; i<=n; ++i) {
		T.push_back(s[i].a);
		T.push_back(s[i].b);
	}

	for (int i=1; i<=nQueries; ++i)
		T.push_back(Q[i].y);

	sort(T.begin(), T.end());
	T.resize(unique(T.begin(), T.end()) - T.begin());

	#define get_pos(P, x) lower_bound(P.begin(), P.end(), x) - P.begin() + 1
	for (int i=1; i<=n; ++i) {
		s[i].a = get_pos(T, s[i].a);
		s[i].b = get_pos(T, s[i].b);
	}

	for (int i=1; i<=nQueries; ++i)
		Q[i].y = get_pos(T, Q[i].y);
	#undef uniq
}

void init() {
	for (int i=1; i<=n; ++i) {
		store_event[s[i].a].push_back(i);
		store_event[s[i].b+1].push_back(-i);
	}

	for (int i=1; i<=nQueries; ++i) {
		q[Q[i].y].push_back(i);
	}

	for (int i=1; i<=k; ++i) {
		++pos[i][-INF];
		++pos[i][INF];
		interval_set.insert(-INF, INF);
	}
}

void add_store(int idx) {
	++pos[s[idx].t][s[idx].x];

	if (pos[s[idx].t][s[idx].x]==1) {
		auto u = pos[s[idx].t].lower_bound(s[idx].x);
		--u;
		auto v = pos[s[idx].t].upper_bound(s[idx].x);
//		debug(u->first);
//        debug(v->first);

		interval_set.erase(u->first, v->first);
		interval_set.insert(u->first, s[idx].x);
		interval_set.insert(s[idx].x, v->first);
	}
}

void remove_store(int idx) {
	--pos[s[idx].t][s[idx].x];

	if (!pos[s[idx].t][s[idx].x]) {
		auto u = pos[s[idx].t].lower_bound(s[idx].x);
		--u;
		auto v = pos[s[idx].t].upper_bound(s[idx].x);
//        debug(u->first);
//        debug(v->first);

		interval_set.erase(u->first, s[idx].x);
		interval_set.erase(s[idx].x, v->first);
		interval_set.insert(u->first, v->first);
        pos[s[idx].t].erase(s[idx].x);
	}
}

int bisect(int x) {
	int l = 0, r = 1e9;

	for (int mid=(l+r)/2; mid!=l && r!=mid; mid=(l+r)/2) {
		if (interval_set.get(x-mid-1)>x+mid)
			l = mid;
		else
			r = mid;
	}

	for (int i=l; i<=r; ++i) {
		if (interval_set.get(x-i-1)<=x+i)
			return i;
	}

	return -1;
}

void solve() {
	for (int i=1; i<=T.size(); ++i) {
		for (auto x : store_event[i]) {
			if (x>0)
				add_store(x);
			else
				remove_store(-x);
		}

//		debug(interval_set.get(0));
		for (auto x : q[i])
			res[x] = bisect(Q[x].l);
	}

	for (int i=1; i<=nQueries; ++i)
		cout << res[i] << '\n';
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".in", "r", stdin);
//		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);

	read_input();
	compress();
	init();
	solve();
}

Compilation message (stderr)

new_home.cpp: In function 'void solve()':
new_home.cpp:239:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<=T.size(); ++i) {
                ~^~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20