oj.uz

Submission #201871

# Submission time Handle Problem Language Result Execution time Memory
201871 2020-02-12T14:12:22 Z maruii New Home (APIO18_new_home) C++14
10 / 100
 3573 ms 98104 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() {
	sort(qin.begin(), qin.end());
	sort(qout.begin(), qout.end());
	sort(qry.begin(), qry.end());
	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));
	}
	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:38: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:53:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (j < qin.size()) {
         ~~^~~~~~~~~~~~
new_home.cpp:58:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (k < qout.size()) {
         ~~^~~~~~~~~~~~~
new_home.cpp:67:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < qin.size() && qin[j].ff <= i.ff) {
          ~~^~~~~~~~~~~~
new_home.cpp:84:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (k < qout.size() && qout[k].ff < i.ff) {
          ~~^~~~~~~~~~~~~
new_home.cpp:103:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (j < qin.size()) {
         ~~^~~~~~~~~~~~
new_home.cpp:108: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 20 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 20 ms 22648 KB Output is correct
5 Correct 22 ms 22648 KB Output is correct
6 Incorrect 22 ms 22648 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 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 20 ms 22648 KB Output is correct
5 Correct 22 ms 22648 KB Output is correct
6 Incorrect 22 ms 22648 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 2119 ms 75288 KB Output is correct
2 Correct 1233 ms 67568 KB Output is correct
3 Correct 1364 ms 98024 KB Output is correct
4 Correct 2064 ms 79080 KB Output is correct
5 Correct 1370 ms 67452 KB Output is correct
6 Correct 1210 ms 67356 KB Output is correct
7 Correct 1360 ms 98104 KB Output is correct
8 Correct 2074 ms 78960 KB Output is correct
9 Correct 2091 ms 72424 KB Output is correct
10 Correct 1523 ms 68396 KB Output is correct
11 Correct 1177 ms 67196 KB Output is correct
12 Correct 1348 ms 68292 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 20 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 20 ms 22648 KB Output is correct
5 Correct 22 ms 22648 KB Output is correct
6 Incorrect 22 ms 22648 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 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 20 ms 22648 KB Output is correct
5 Correct 22 ms 22648 KB Output is correct
6 Incorrect 22 ms 22648 KB Output isn't correct
7 Halted 0 ms 0 KB -