Submission #490196

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
490196	2021-11-26T07:51:48 Z	8e7	New Home (APIO18_new_home)	C++17	10 / 100	449 ms	42416 KB

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 < range.size();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 2 8 10
1 1
5 1
7 1
3 1

1 1 1
100000000 1 1 1
1 1
*/

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for (int i = 0;i < range.size();i++) {
      |                 ~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Incorrect	3 ms	4940 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Incorrect	3 ms	4940 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	315 ms	27512 KB	Output is correct
2	Correct	436 ms	26224 KB	Output is correct
3	Correct	333 ms	42344 KB	Output is correct
4	Correct	358 ms	41444 KB	Output is correct
5	Correct	449 ms	38200 KB	Output is correct
6	Correct	439 ms	38576 KB	Output is correct
7	Correct	312 ms	42416 KB	Output is correct
8	Correct	346 ms	41388 KB	Output is correct
9	Correct	331 ms	41068 KB	Output is correct
10	Correct	434 ms	39660 KB	Output is correct
11	Correct	349 ms	38804 KB	Output is correct
12	Correct	348 ms	39776 KB	Output is correct