Submission #111875

#	Time	Username	Problem	Language	Result	Execution time	Memory
111875		square1001	New Home (APIO18_new_home)	C++14	100 / 100	2041 ms	78176 KiB

new_home

#include <set>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1012345678;
class segment {
	public:
	int l, r, x;
	segment() : l(0), r(0), x(0) {};
	segment(int l_, int r_, int x_) : l(l_), r(r_), x(x_) {};
	bool operator<(const segment& s) const {
		if(l != s.l) return l < s.l;
		if(r != s.r) return r < s.r;
		return x < s.x;
	}
};
class query {
	public:
	int l, r, x, w;
	query() : l(0), r(0), x(0), w(0) {};
	query(int l_, int r_, int x_, int w_) : l(l_), r(r_), x(x_), w(w_) {};
	bool operator<(const query& q) const {
		if(x != q.x) return x < q.x;
		return w < q.w;
	}
};
class segtree {
	private:
	int sz;
	vector<int> val;
	public:
	segtree() : sz(0), val(vector<int>()) {};
	segtree(int sz_) {
		sz = 1;
		while(sz < sz_) sz *= 2;
		val = vector<int>(sz * 2, -inf);
	}
	void update(int l, int r, int x) {
		l += sz;
		r += sz;
		while(l != r) {
			if(l & 1) val[l] = max(val[l], x), ++l;
			if(r & 1) --r, val[r] = max(val[r], x);
			l >>= 1, r >>= 1;
		}
	}
	int get(int pos) {
		pos += sz;
		int ans = -inf;
		while(pos >= 1) {
			ans = max(ans, val[pos]);
			pos >>= 1;
		}
		return ans;
	}
};
vector<int> solve(int N, int K, int Q, vector<int> X, vector<int> T, vector<int> A, vector<int> B, vector<int> L, vector<int> Y) {
	vector<int> comp = { 0, inf };
	vector<vector<int> > G(K);
	for(int i = 0; i < N; ++i) {
		++B[i], --T[i];
		comp.push_back(A[i]);
		comp.push_back(B[i]);
		X[i] *= 2;
		G[T[i]].push_back(i);
	}
	for(int i = 0; i < Q; ++i) {
		L[i] *= 2;
	}
	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());
	int S = comp.size();
	for(int i = 0; i < N; ++i) {
		A[i] = lower_bound(comp.begin(), comp.end(), A[i]) - comp.begin();
		B[i] = lower_bound(comp.begin(), comp.end(), B[i]) - comp.begin();
	}
	for(int i = 0; i < Q; ++i) {
		Y[i] = lower_bound(comp.begin(), comp.end(), Y[i] + 1) - comp.begin() - 1;
	}
	vector<query> qs;
	for(int i = 0; i < K; ++i) {
		set<segment> st;
		st.insert(segment(0, S, -inf));
		vector<segment> iniqs;
		for(int j : G[i]) {
			iniqs.push_back(segment(A[j], B[j], X[j]));
		}
		sort(iniqs.begin(), iniqs.end(), [](segment s1, segment s2) { return s1.x < s2.x; });
		int cnt = 0;
		for(segment s : iniqs) {
			set<segment>::iterator it = st.lower_bound(segment(s.l, s.r, s.x));
			if(it != st.begin()) --it;
			vector<segment> nst;
			while(it != st.end() && it->l < s.r) {
				segment t = *it;
				int al = max(t.l, s.l), ar = min(t.r, s.r);
				if(al >= ar) {
					++it;
					continue;
				}
				++cnt;
				it = st.erase(it);
				qs.push_back(query(al, ar, (s.x + t.x) / 2, (s.x - t.x) / 2));
				nst.push_back(segment(al, ar, s.x));
				if(t.l < al) nst.push_back(segment(t.l, al, t.x));
				if(ar < t.r) nst.push_back(segment(ar, t.r, t.x));
			}
			if(!nst.empty()) {
				sort(nst.begin(), nst.end());
				int pre = nst[0].l;
				vector<segment> nnst;
				for(int i = 1; i <= nst.size(); ++i) {
					if(i == nst.size() || nst[i - 1].x != nst[i].x) {
						nnst.push_back(segment(pre, nst[i - 1].r, nst[i - 1].x));
						pre = nst[i - 1].r;
					}
				}
				st.insert(nnst.begin(), nnst.end());
			}
		}
		for(segment s : st) {
			qs.push_back(query(s.l, s.r, (inf + s.x) / 2, (inf - s.x) / 2));
		}
	}
	for(int i = 0; i < Q; ++i) {
		qs.push_back(query(Y[i], Y[i] + 1, L[i], -(i + 1)));
	}
	sort(qs.begin(), qs.end());
	segtree seg(S);
	for(query i : qs) {
		if(i.w >= 0 && i.x - i.w == -inf) {
			seg.update(i.l, i.r, i.x + i.w);
		}
	}
	vector<int> ans(Q, -1);
	for(query i : qs) {
		if(i.w < 0) {
			ans[-i.w - 1] = max(ans[-i.w - 1], seg.get(i.l) - i.x);
		}
		else {
			seg.update(i.l, i.r, i.x + i.w);
		}
	}
	reverse(qs.begin(), qs.end());
	seg = segtree(S);
	for(query i : qs) {
		if(i.w >= 0 && i.x + i.w == inf) {
			seg.update(i.l, i.r, -(i.x - i.w));
		}
	}
	for(query i : qs) {
		if(i.w < 0) {
			ans[-i.w - 1] = max(ans[-i.w - 1], i.x - (-seg.get(i.l)));
		}
		else {
			seg.update(i.l, i.r, -(i.x - i.w));
		}
	}
	for(int i = 0; i < Q; ++i) {
		if(ans[i] > inf / 3) ans[i] = -1;
		else ans[i] /= 2;
	}
	return ans;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, K, Q;
	cin >> N >> K >> Q;
	vector<int> X(N), T(N), A(N), B(N), L(Q), Y(Q);
	for(int i = 0; i < N; ++i) {
		cin >> X[i] >> T[i] >> A[i] >> B[i];
	}
	for(int i = 0; i < Q; ++i) {
		cin >> L[i] >> Y[i];
	}
	vector<int> ans = solve(N, K, Q, X, T, A, B, L, Y);
	for(int i = 0; i < Q; ++i) {
		cout << ans[i] << '\n';
	}
	return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'std::vector<int> solve(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
new_home.cpp:114:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i <= nst.size(); ++i) {
                    ~~^~~~~~~~~~~~~
new_home.cpp:115:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(i == nst.size() || nst[i - 1].x != nst[i].x) {
         ~~^~~~~~~~~~~~~

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