oj.uz

Submission #201911

# Submission time Handle Problem Language Result Execution time Memory
201911 2020-02-12T19:00:32 Z maruii New Home (APIO18_new_home) C++14
10 / 100
 3545 ms 86508 KB 
#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;
			auto it = MS[c].lower_bound(x);
			xx.emplace_back((*it + x) / 2, c);
			--it;
			xx.emplace_back((x + *it) / 2, c);
			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;
			MS[c].erase(MS[c].find(x));
			++k;
		}
	}
	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

new_home.cpp: In function 'void solve()':
new_home.cpp:35:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < qin.size() && qin[j].ff <= i.ff) {
          ~~^~~~~~~~~~~~
new_home.cpp:44:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (k < qout.size() && qout[k].ff < i.ff) {
          ~~^~~~~~~~~~~~~
new_home.cpp:50:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (j < qin.size()) {
         ~~^~~~~~~~~~~~
new_home.cpp:55:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (k < qout.size()) {
         ~~^~~~~~~~~~~~~
new_home.cpp:64:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < qin.size() && qin[j].ff <= i.ff) {
          ~~^~~~~~~~~~~~
new_home.cpp:81:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (k < qout.size() && qout[k].ff < i.ff) {
          ~~^~~~~~~~~~~~~
new_home.cpp:100:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (j < qin.size()) {
         ~~^~~~~~~~~~~~
new_home.cpp:105:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (k < qout.size()) {
         ~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 22648 KB Output is correct
2 Correct 20 ms 22648 KB Output is correct
3 Correct 20 ms 22648 KB Output is correct
4 Correct 21 ms 22680 KB Output is correct
5 Correct 20 ms 22648 KB Output is correct
6 Incorrect 23 ms 22776 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 22648 KB Output is correct
2 Correct 20 ms 22648 KB Output is correct
3 Correct 20 ms 22648 KB Output is correct
4 Correct 21 ms 22680 KB Output is correct
5 Correct 20 ms 22648 KB Output is correct
6 Incorrect 23 ms 22776 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2132 ms 64016 KB Output is correct
2 Correct 1227 ms 57204 KB Output is correct
3 Correct 1332 ms 86508 KB Output is correct
4 Correct 2070 ms 67672 KB Output is correct
5 Correct 1248 ms 57200 KB Output is correct
6 Correct 1230 ms 57228 KB Output is correct
7 Correct 1346 ms 86376 KB Output is correct
8 Correct 2063 ms 67508 KB Output is correct
9 Correct 2075 ms 60924 KB Output is correct
10 Correct 1496 ms 57552 KB Output is correct
11 Correct 1136 ms 56944 KB Output is correct
12 Correct 1317 ms 57304 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3545 ms 58332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 22648 KB Output is correct
2 Correct 20 ms 22648 KB Output is correct
3 Correct 20 ms 22648 KB Output is correct
4 Correct 21 ms 22680 KB Output is correct
5 Correct 20 ms 22648 KB Output is correct
6 Incorrect 23 ms 22776 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 22648 KB Output is correct
2 Correct 20 ms 22648 KB Output is correct
3 Correct 20 ms 22648 KB Output is correct
4 Correct 21 ms 22680 KB Output is correct
5 Correct 20 ms 22648 KB Output is correct
6 Incorrect 23 ms 22776 KB Output isn't correct
7 Halted 0 ms 0 KB -