Submission #490195

#	Time	Username	Problem	Language	Result	Execution time	Memory
490195		8e7	New Home (APIO18_new_home)	C++17	0 / 100	446 ms	27568 KiB

new_home

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <assert.h>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
void debug(){cout << endl;};
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define maxn 300005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<29;
struct segtree{ //PURQ segtree
	int seg[4*maxn];
	void init(int cur, int l, int r) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = inf;
			return;
		}
		int m = (l + r) / 2;
		init(cur*2, l, m), init(cur*2+1, m, r);
		seg[cur] = inf;
	}
	void modify(int cur, int l, int r, int ind, int val) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = val;
			return;
		}
		int m = (l + r) / 2;
		if (ind < m)modify(cur*2, l, m, ind, val);
		else modify(cur*2+1, m, r, ind, val);
		seg[cur] = min(seg[cur*2], seg[cur*2+1]);
	}
	int query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return inf;
		if (ql <= l && qr >= r) return seg[cur];
		int m = (l + r) / 2;
		return min(query(cur*2, l, m, ql, qr), query(cur*2+1, m, r, ql, qr));
	}
} sl, sr;
struct obj{
	int x, t, a, b;
	obj(){x = t = a = b = 0;}
	obj(int xx, int tt, int aa, int bb){x = xx, t = tt, a = aa, b = bb;}
} st[maxn];
struct query{
	int pos, ti, id;
	query(){pos = ti = id = 0;}
	query(int x, int y, int z){pos = x, ti = y, id = z;}
};
int nxt[maxn], rcol[maxn];
int ans[maxn];
vector<pii> range;
vector<int> pose; //positions set

vector<query> que;

void compress(vector<int> &v) {
	sort(v.begin(), v.end());
	v.resize(int(unique(v.begin(), v.end()) - v.begin()));
}
int main() {
	io
	int n, k, q;	
	cin >> n >> k >> q;
	for (int i = 0;i < n;i++) {
		cin >> st[i].x >> st[i].t >> st[i].a >> st[i].b;
	}
	que.resize(q);
	for (int i = 0;i < q;i++) {
		cin >> que[i].pos >> que[i].ti;
		que[i].id = i;
	}
	sort(st, st + n, [&](obj x, obj y){return x.x < y.x;});		
	for (int i = 1;i <= k;i++) rcol[i] = inf;
	for (int i = n - 1;i >= 0;i--) {
		nxt[i] = rcol[st[i].t];	
		rcol[st[i].t] = st[i].x;
	}
	int rig = 0;
	for (int i = 1;i <= k;i++) rig = max(rig, rcol[i]);
	for (int i = 0;i < n;i++) {
		//if (rig == inf) continue;
		range.push_back({(st[i].x + rig), rig - st[i].x});
		//debug(st[i].x, rig);
		pose.push_back(st[i].x + rig);	
		rig = max(rig, nxt[i]);	
	}
	compress(pose);	
	int siz = pose.size();	
	sl.init(1, 0, siz), sr.init(1, 0, siz);	
	auto lb = [&] (int x) {
		return lower_bound(pose.begin(), pose.end(), x) - pose.begin();
	};
	for (int i = 0;i < siz;i++) {
		int ind = lb(range[i].ff);
		//debug(range[i].ff, range[i].ss, ind, siz);
		sl.modify(1, 0, siz, ind, range[i].ss - range[i].ff);
		sr.modify(1, 0, siz, ind, range[i].ss + range[i].ff);
	}	
	for (auto qq:que) {
		int ind = lb(2*qq.pos);
		//debug(qq.id, ind, qq.pos);
		//debug(sl.query(1, 0, siz, 0, ind), sr.query(1, 0, siz, ind, siz));
		ans[qq.id] = min(sl.query(1, 0, siz, 0, ind) + 2*qq.pos, sr.query(1, 0, siz, ind, siz) - 2*qq.pos);
	}
	for (int i = 0;i < q;i++) {
		ans[i] /= 2;
		cout << (ans[i] > 100000000 ? -1 : ans[i]) << "\n";
	}
}
/*

4 2 4
3 1 1 10
9 2 1 4
7 2 1 7
4 1 8 10
1 1
5 1
2 1
3 1

1 1 1
100000000 1 1 1
1 1
*/

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