Submission #201912

#	Time	Username	Problem	Language	Result	Execution time	Memory
201912		maruii	New Home (APIO18_new_home)	C++14	80 / 100	5045 ms	100356 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

const int SIZE = 1 << 20;
struct ST {
	int A[2 * SIZE];
	void init() { fill(A, A + 2 * SIZE, -1e9); }
	void update(int x, int v) {
		x += SIZE; A[x] = v;
		for (x >>= 1; x; x >>= 1) A[x] = max(A[x << 1], A[x << 1 | 1]);
	}
	int query(int s, int e) {
		int ret = -1e9;
		for (s += SIZE, e += SIZE; s <= e; s >>= 1, e >>= 1) {
			if ( s & 1) ret = max(ret, A[s++]);
			if (~e & 1) ret = max(ret, A[e--]);
		}
		return ret;
	}
} seg;

int N, K, Q;
vector<pair<int, pii> > qin, qout, qry;
vector<pii> xx;
int ans[300005];
multiset<int> MS[300005];

void solve() {
	xx.clear();
	seg.init();
	int j = 0, k = 0;
	for (auto i : qry) {
		while (j < qin.size() && qin[j].ff <= i.ff) {
			int x = qin[j].ss.ff, c = qin[j].ss.ss;
			++j;
			auto it = MS[c].lower_bound(x);
			if (*it != x) {
				xx.emplace_back((*it + x) / 2, c);
				--it;
				xx.emplace_back((x + *it) / 2, c);
			}
			MS[c].insert(x);
		}
		while (k < qout.size() && qout[k].ff < i.ff) {
			int x = qout[k].ss.ff, c = qout[k].ss.ss;
			MS[c].erase(MS[c].find(x));
			++k;
			auto it = MS[c].lower_bound(x);
			if (*it != x) {
				auto jt = it;
				--jt;
				xx.emplace_back((*it + *jt) / 2, c);
			}
		}
	}
	while (j < qin.size()) {
		int x = qin[j].ss.ff, c = qin[j].ss.ss;
		MS[c].insert(x);
		++j;
	}
	while (k < qout.size()) {
		int x = qout[k].ss.ff, c = qout[k].ss.ss;
		MS[c].erase(MS[c].find(x));
		++k;
	}
	sort(xx.begin(), xx.end());
	j = k = 0;
	int cnt = 0;
	for (auto i : qry) {
		while (j < qin.size() && qin[j].ff <= i.ff) {
			int x = qin[j].ss.ff, c = qin[j].ss.ss, t, p, q;
			auto it = MS[c].lower_bound(x);
			if (MS[c].size() == 2) ++cnt;
			if (*it != x) {
				auto jt = it;
				--jt;
				t = lower_bound(xx.begin(), xx.end(), pii((*it + *jt) / 2, c)) - xx.begin();
				p = lower_bound(xx.begin(), xx.end(), pii((*it + x) / 2, c)) - xx.begin();
				q = lower_bound(xx.begin(), xx.end(), pii((x + *jt) / 2, c)) - xx.begin();
				if (MS[c].size() > 2) seg.update(t, -1e9);
				seg.update(p, *it);
				seg.update(q, x);
			}
			MS[c].insert(x);
			++j;
		}
		while (k < qout.size() && qout[k].ff < i.ff) {
			int x = qout[k].ss.ff, c = qout[k].ss.ss, t, p, q;
			MS[c].erase(MS[c].find(x));
			++k;
			auto it = MS[c].lower_bound(x);
			if (*it != x) {
				auto jt = it;
				--jt;
				t = lower_bound(xx.begin(), xx.end(), pii((*it + *jt) / 2, c)) - xx.begin();
				p = lower_bound(xx.begin(), xx.end(), pii((*it + x) / 2, c)) - xx.begin();
				q = lower_bound(xx.begin(), xx.end(), pii((x + *jt) / 2, c)) - xx.begin();
				if (MS[c].size() > 2) seg.update(t, *it);
				seg.update(p, -1e9);
				seg.update(q, -1e9);
			}
			if (MS[c].size() == 2) --cnt;
		}
		if (cnt == K) ans[i.ss.ss] = max(ans[i.ss.ss], (seg.query(0, lower_bound(xx.begin(), xx.end(), pii(i.ss.ff + 1, 0)) - xx.begin() - 1) - i.ss.ff) / 2);
	}
	while (j < qin.size()) {
		int x = qin[j].ss.ff, c = qin[j].ss.ss;
		MS[c].insert(x);
		++j;
	}
	while (k < qout.size()) {
		int x = qout[k].ss.ff, c = qout[k].ss.ss;
		MS[c].erase(MS[c].find(x));
		++k;
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> K >> Q;
	fill(ans, ans + Q, -1);
	for (int i = 1; i <= K; ++i) {
		MS[i].insert(1e9);
		MS[i].insert(-1e9);
	}
	for (int i = 0; i < N; ++i) {
		int a, b, c, d; cin >> a >> b >> c >> d;
		a *= 2;
		qin.emplace_back(c, pii(a, b));
		qout.emplace_back(d, pii(a, b));
	}
	for (int i = 0; i < Q; ++i) {
		int a, b; cin >> a >> b;
		a *= 2;
		qry.emplace_back(b, pii(a, i));
	}
	sort(qin.begin(), qin.end());
	sort(qout.begin(), qout.end());
	sort(qry.begin(), qry.end());
	solve();
	for (auto &i : qin) i.ss.ff = -i.ss.ff;
	for (auto &i : qout) i.ss.ff = -i.ss.ff;
	for (auto &i : qry) i.ss.ff = -i.ss.ff;
	solve();
	for (int i = 0; i < Q; ++i) printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'void solve()':
new_home.cpp:36:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < qin.size() && qin[j].ff <= i.ff) {
          ~~^~~~~~~~~~~~
new_home.cpp:47:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (k < qout.size() && qout[k].ff < i.ff) {
          ~~^~~~~~~~~~~~~
new_home.cpp:59:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (j < qin.size()) {
         ~~^~~~~~~~~~~~
new_home.cpp:64:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (k < qout.size()) {
         ~~^~~~~~~~~~~~~
new_home.cpp:73:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < qin.size() && qin[j].ff <= i.ff) {
          ~~^~~~~~~~~~~~
new_home.cpp:90:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (k < qout.size() && qout[k].ff < i.ff) {
          ~~^~~~~~~~~~~~~
new_home.cpp:109:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (j < qin.size()) {
         ~~^~~~~~~~~~~~
new_home.cpp:114:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (k < qout.size()) {
         ~~^~~~~~~~~~~~~

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