Submission #676619

#	Time	Username	Problem	Language	Result	Execution time	Memory
676619		ymm	New Home (APIO18_new_home)	C++17	45 / 100	3135 ms	122812 KiB

new_home

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

#define int ll
#define pii pll

enum EventType {Rem, Add, Query};

struct Event {
	int time;
	EventType type;
	int store;
	int pos;
	int query_idx;
};

bool operator<(const Event &a, const Event &b) {
	return a.time < b.time || a.time == b.time && a.type < b.type;
}

vector<Event> evs;
vector<set<pii>> type_list;

struct Seg {
	int *t;
	int begin, end;
	
	void init(int b, int e) {
		t = new int[4 * (e-b)];
		fill(t, t + 4*(e-b), INT_MIN);
		begin = b;
		end = e;
	}
	void up_impl(int p, int x, int i, int b, int e) {
		if (e-b==1) {
			t[i] = x;
			return;
		}
		if (p < (b+e)/2)
			up_impl(p, x, 2*i+1, b, (b+e)/2);
		else
			up_impl(p, x, 2*i+2, (b+e)/2, e);
		t[i] = max(t[2*i+1], t[2*i+2]);
	}
	int get_impl(int l, int r, int i, int b, int e) {
		if (l <= b && e <= r)
			return t[i];
		if (r <= b || e <= l)
			return INT_MIN;
		return max(get_impl(l, r, 2*i+1, b, (b+e)/2),
		           get_impl(l, r, 2*i+2, (b+e)/2, e));
	}

	void up(int p, int x) { return up_impl(p, x, 0, begin, end); }
	int get(int l, int r) { return get_impl(l, r, 0, begin, end); }
} next_right;

int cnt_types, cnt_stores, cnt_queries;
vector<int> store_poses;

struct Store {
	int type;
	int pos;
	int b, e;
};
bool operator<(const Store &a, const Store &b) { return a.pos < b.pos; }
vector<Store> stores;

vector<int> ans;

void handle_add(Event ev)
{
	Store s = stores[ev.store];
	auto &list = type_list[s.type];
	auto it = list.upper_bound({s.pos, ev.store});
	int p = it == list.end()? INT_MAX: it->first;
	--it;
	next_right.up(it->second, s.pos);
	next_right.up(ev.store, p);
	list.insert({s.pos, ev.store});
}
void handle_rem(Event ev)
{
	Store s = stores[ev.store];
	auto &list = type_list[s.type];
	auto it = list.upper_bound({s.pos, ev.store});
	int p = it == list.end()? INT_MAX: it->first;
	--it; --it;
	next_right.up(it->second, p);
	next_right.up(ev.store, INT_MIN);
	list.erase({s.pos, ev.store});
}
void handle_query(Event ev)
{
	if (next_right.get(-cnt_types, 0) == INT_MAX) {
		ans[ev.query_idx] = -1;
		return;
	}
	int l = 0, r = store_poses.back();
	auto get = [&](int e) {
		e = lower_bound(store_poses.begin(), store_poses.end(), e) - store_poses.begin();
		return next_right.get(-cnt_stores, e);
	};
	while (l < r) {
		int m = (l + r)/2;
		int b = ev.pos - m, e = ev.pos + m + 1;
		if (get(b) < e)
			r = m;
		else
			l = m+1;
	}
	ans[ev.query_idx] = l;
}

signed main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> cnt_stores >> cnt_types >> cnt_queries;
	Loop (i,0,cnt_stores) {
		Store s;
		cin >> s.pos >> s.type >> s.b >> s.e;
		--s.pos; --s.b;
		stores.push_back(s);
		store_poses.push_back(s.pos);
	}
	sort(stores.begin(), stores.end());
	sort(store_poses.begin(), store_poses.end());
	Loop (i,0,cnt_stores) {
		evs.push_back({
			.time = stores[i].b,
			.type = Add,
			.store = i,
			.pos = stores[i].pos,
			.query_idx = -1,
		});
		evs.push_back({
			.time = stores[i].e,
			.type = Rem,
			.store = i,
			.pos = stores[i].pos,
			.query_idx = -1,
		});
	}
	Loop (i,0,cnt_queries) {
		int l, y;
		cin >> l >> y;
		--l; --y;
		evs.push_back({
			.time = y,
			.type = Query,
			.store = -1,
			.pos = l,
			.query_idx = i,
		});
	}
	sort(evs.begin(), evs.end());
	ans.resize(cnt_queries);
	type_list.resize(cnt_types+1);
	next_right.init(-cnt_types, cnt_stores);
	Loop (i,-cnt_types,0) {
		type_list[-i].insert({i, i});
		next_right.up(i, INT_MAX);
	}
	for (Event ev : evs) {
		switch (ev.type) {
		case Add:	handle_add(ev);		break;
		case Rem:	handle_rem(ev);		break;
		case Query:	handle_query(ev);	break;
		}
	}
	Loop (i,0,cnt_queries)
		cout << ans[i] << '\n';
}

Compilation message (stderr)

new_home.cpp: In function 'bool operator<(const Event&, const Event&)':
new_home.cpp:23:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   23 |  return a.time < b.time || a.time == b.time && a.type < b.type;
      |                            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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