Submission #63388

#	Time	Username	Problem	Language	Result	Execution time	Memory
63388		memikakizaki	New Home (APIO18_new_home)	C++14	47 / 100	5092 ms	461024 KiB

new_home

#include <bits/stdc++.h>
#define long long long
using namespace std;
const int N = 3e5+1, INF = 1e9;

int n, k, q, res[N];
vector<tuple<int,int,int,int> > ops;
vector<tuple<int,int,int> > events;
// ops = initial sorting of intervals, events for compression after determining coords and calculation
map<int, int> points[N];
vector<map<int, int> > st;
// for cc
vector<int> vals;
unordered_map<int, int> rev;
// segment tree
vector<int> t;

void build(int n) { t = vector<int>(2*n, INF); }
void update(int i, int v) {
	int n = t.size() >> 1;
	for(t[i += n] = v; i > 1; i >>= 1) t[i >> 1] = min(t[i], t[i^1]);
}
int query(int l, int r) {
	int n = t.size() >> 1;
	int ret = INF;
	for(l += n, r += n+1; l < r; l >>= 1, r >>= 1) {
		if(l & 1) ret = min(t[l++], ret);
		if(r & 1) ret = min(t[--r], ret);
	}
	return ret;
}
/* int query_test(int tl, int tr) { */
/* 	int ans = INF; */
/* 	cout << "list:\n"; */
/* 	for(int i = tl; i <= tr; i++) if(!st[i].empty()) ans = min(st[i].begin()->first, ans), cout << st[i].begin()->first << ' ' << st[i].begin()->second << endl; */
/* 	cout << endl; */
/* 	return ans; */
/* } */

inline void add_line(int l, int r) { events.emplace_back(0, l, r); }
inline void rem_line(int l, int r) { events.emplace_back(1, l, r); }
void add(int x, int ti, bool doceil) {
	if(points[ti].count(x)) {
		++points[ti][x];
		return;
	}
	auto it = points[ti].upper_bound(x);
	// init vals
	int pre_val, curr_val;
	bool set_pre = false, set_curr = false;
	if(it != points[ti].begin()) {
		set_pre = true;
		pre_val = prev(it)->first;
	}
	if(it != points[ti].end()) {
		set_curr = true;
		curr_val = it->first;
	}
	// process
	if(set_pre) {
		if(it != points[ti].end()) rem_line(pre_val, (pre_val + curr_val - doceil) / 2);
		add_line(pre_val, (pre_val + x - doceil) / 2);
	}
	if(it != points[ti].end()) add_line(x, (curr_val + x - doceil) / 2);
	++points[ti][x];
	// cout << endl;
}
void rem(int x, int ti, bool doceil) {
	if(points[ti].count(x) && points[ti][x] > 1) {
		--points[ti][x];
		return;
	}
	auto it = points[ti].find(x);
	// init values
	int pre_val, nxt_val;
	bool set_pre = false, set_nxt = false;
	if(it != points[ti].begin()) {
		set_pre = true;
		pre_val = prev(it)->first;
	}
	if(next(it) != points[ti].end()) {
		set_nxt = true;
		nxt_val = next(it)->first;
	}
	// process
	if(set_pre) {
		if(set_nxt) add_line(pre_val, (pre_val + nxt_val - doceil) / 2);
		rem_line(pre_val, (pre_val + x - doceil) / 2);
	}
	if(set_nxt) rem_line(x, (nxt_val + x - doceil) / 2);
	points[ti].erase(x);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k >> q;
	for(int i = 0, x, t, a, b; i < n; i++) {
		cin >> x >> t >> a >> b;
		ops.emplace_back(a, 0, x, t);
		ops.emplace_back(b+1, 1, x, t);
	}
	for(int i = 0, l, y; i < q; i++) {
		cin >> l >> y;
		ops.emplace_back(y, 2, l, i);
	}
	sort(ops.begin(), ops.end());
	for(int i = 1; i <= k; i++) {
		points[i][-INF] = 1;
		points[i][INF] = 1;
	}
	for(auto &tt: ops) {
		int inst, x, ti;
		tie(ignore, inst, x, ti) = tt;
		if(inst == 0) add(x, ti, 0);
		else if(inst == 1) rem(x, ti, 0);
		else events.emplace_back(2, x, ti);
	}
	for(auto &tt: ops) {
		int inst, x, ti;
		tie(ignore, inst, x, ti) = tt;
		if(inst == 0) add(-x, ti, 1);
		else if(inst == 1) rem(-x, ti, 1);
		else events.emplace_back(2, -x, ti);
	}
	vals.reserve(2 * events.size() + 10);
	for(auto &tt: events) {
		int inst, l, r;
		tie(inst, l, r) = tt;
		if(inst != 2) vals.push_back(r);
		vals.push_back(l);
	}
	vals.push_back(-INF);
	vals.push_back(0);
	vals.push_back(INF);
	sort(vals.begin(), vals.end());
	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
	for(int i = 0; i < vals.size(); i++) rev[vals[i]] = i;

	st.resize(vals.size());
	build(vals.size());
	update(vals.size()-1, 0);
	update(rev[0], -INF);
	st[vals.size()-1][0] = k; // INF must be even
	st[rev[0]][-INF] = k;
	for(auto &tt: events) {
		int inst, l, r;
		tie(inst, l, r) = tt;
		// cout << inst << ' ' << l << ' ' << r << endl;
		if(inst == 0) {
			int rc = rev[r];
			++st[rc][l];
			update(rc, st[rc].begin()->first);
		} else if(inst == 1) {
			int rc = rev[r];
			--st[rc][l];
			if(!st[rc][l]) st[rc].erase(l);
			if(!st[rc].empty()) update(rc, st[rc].begin()->first);
			else update(rc, INF);
		} else {
			int x = l, i = r;
			int ret = query(rev[x], vals.size()-2);
			// cout << endl;
			res[i] = max(x-ret, res[i]);
		}
	}
	for(int i = 0; i < q; i++) cout << (res[i] >= INF/2 ? -1 : res[i]) << '\n';
}

Compilation message (stderr)

new_home.cpp: In function 'void add(int, int, bool)':
new_home.cpp:50:24: warning: variable 'set_curr' set but not used [-Wunused-but-set-variable]
  bool set_pre = false, set_curr = false;
                        ^~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:138:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < vals.size(); i++) rev[vals[i]] = i;
                 ~~^~~~~~~~~~~~~
new_home.cpp: In function 'void add(int, int, bool)':
new_home.cpp:64:51: warning: 'curr_val' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if(it != points[ti].end()) add_line(x, (curr_val + x - doceil) / 2);
                                          ~~~~~~~~~^~~

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