Submission #49132

#	Time	Username	Problem	Language	Result	Execution time	Memory
49132		samuelfgs96	New Home (APIO18_new_home)	C++11	100 / 100	4077 ms	71432 KiB

new_home

#include <bits/stdc++.h>
 
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 0x3f3f3f3f
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 500000;

int x[N], t[N], a[N], b[N], l[N], y[N];
int ans[N];
bool flag;
vector <pii> values;
struct segtree {
	vector <int> seg;
	int n, k, a, b, t;
	segtree() { }
	segtree(int n, int t) : n(n), t(t) {
		if (t)
			seg.resize(4*n+1, INT_MAX);
		else
			seg.resize(4*n+1, -1);
	}
	int operador (int x, int y) {
		return t ? min(x, y) : max(x, y);
	}
	void update (int r, int i, int j) {
		if (i > b or j < a) return ;
		if (i >= a and j <= b) {
			seg[r] = k;
			return ;
		}
		int mid = (i + j) / 2;
		update (r*2, i, mid);
		update (r*2+1, mid+1, j);
		seg[r] = operador(seg[r*2], seg[r*2+1]);
//		if (t == 1) cout << r << " " << i << " " << j << ": " << seg[r] << endl;
	}
	int query_left (int r, int i, int j) {
		if (i > b or j < a) return -1;
		int mid = (i + j) / 2;
		if (i >= a and j <= b) {
			if (seg[r] < k) return -1;
			if (i == j) return i;
			
			if (seg[r*2] >= k) return query_left(r*2, i, mid);
			return query_left(r*2+1, mid+1, j);
		}
		int l = query_left(r*2, i, mid);
		return l == -1 ? query_left(r*2+1, mid+1, j) : l;
	}
	int query_right (int r, int i, int j) {
//		printf("query_right i %d j %d a %d b %d segr %d\n", i, j, a, b, seg[r]);
		if (i > b or j < a) return -1;
		int mid = (i + j) / 2;
		if (i >= a and j <= b) {
			if (seg[r] > k) return -1;
			if (i == j) return i;
			if (seg[r*2+1] <= k) return query_right(r*2+1, mid+1, j);
			return query_right(r*2, i, mid);
		}
		int l = query_right(r*2+1, mid+1, j);
		return l == -1 ? query_right(r*2, i, mid) : l;
	}
	void update (int id, int val) {
//		printf("update \t st %d id %d x %d val %d\n", t, id, x[id], val);
		a = b = lower_bound(values.begin(), values.end(), mp(x[id], id)) - values.begin();
//		printf("\t a %d b %d\n", a, b);
		k = val;
		update (1, 0, n-1);
	}
	int query_left (int pos, int val) {
		a = 0;
		b = upper_bound(values.begin(), values.end(), mp(pos, INF)) - values.begin() - 1;
		if (a > b) return -1;
		k = val;
		return query_left (1, 0, n-1);
	}
	int query_right (int pos, int val) {
		a = lower_bound(values.begin(), values.end(), mp(pos, -1)) - values.begin();
		b = n-1;
		if (a > b) return -1;
		k = val;
		if (flag)
		cout << a << " " << b << " " << k << " " << seg[1] << endl;
		return query_right(1, 0, n-1);
	}
} st[2];

set <pii> active[N];
set<pii>::iterator it;
//left  update 0
//right update 1
void add (int left, int right) {
	if (x[left] == x[right]) {
		st[0].update(left, x[left]);
		st[1].update(right, x[right]);
		return ;
	}
	int mid = (x[left] + x[right]) / 2;
	st[0].update(left, mid);
	st[1].update(right, mid+1);
}
void remove (int left, int right) {
	st[0].update(left, -1);
	st[1].update(right, INF);
}
int main (void) {
	int n, k, q;
	scanf("%d %d %d", &n, &k, &q);
	vector < tuple<int, int, int> > evt;
	for (int i = 0; i < n; i++) {
		scanf("%d %d %d %d", x+i, t+i, a+i, b+i);
		evt.eb(a[i], 0, i);
		evt.eb(b[i], 2, i);
		values.eb(x[i], i);
	}
	for (int i = 0; i < q; i++) {
		scanf("%d %d", l+i, y+i);
//		cout << l[i] << " " << y[i] << endl;
		evt.eb(y[i], 1, i);
	}
	sort(evt.begin(), evt.end());
	sort(values.begin(), values.end());
//	for (int i = 0; i < n; i++)
//		printf("%d: %d %d\n", i, values[i].fi, values[i].se);
//	printf("------------\n");
	st[0] = segtree(n, 0); //maximo
	st[1] = segtree(n, 1); //minimo
	int cnt = 0;
	int w = 0;
	for (int i = 0; i < evt.size(); i++) {
		int coord, tipo, id; tie(coord, tipo, id) = evt[i];
//		cout << coord << " " << tipo << " " << id << endl;
		if (!tipo) { //inserir
//			printf("add t %d x %d\n", t[id], x[id]);
			if (active[t[id]].empty()) {
				st[0].update(id, INF);
				st[1].update(id, -1);
				active[t[id]].insert(mp(x[id], id));
				cnt++;
				continue;
			}
			it = active[t[id]].lower_bound(mp(x[id], id));
			if (it != active[t[id]].end()) add(id, it->se);
			else st[0].update(id, INF);

			if (it != active[t[id]].begin()) {
				it--;
				add(it->se, id);
			} else st[1].update(id, -1);
			active[t[id]].insert(mp(x[id], id));
		} else if (tipo == 2) {
//			printf("rem t %d x %d\n", t[id], x[id]);
			it = active[t[id]].lower_bound(mp(x[id], id+1));
			if (it != active[t[id]].end()) remove(id, it->se);
			else st[0].update(id, -1);

			it = active[t[id]].lower_bound(mp(x[id], id));
			if (it != active[t[id]].begin()) {
				it--;
				remove(it->se, id);
			} else st[1].update(id, INF);

			active[t[id]].erase(mp(x[id], id));

			if (active[t[id]].empty()) {
				cnt--;
				continue;
			}
			int l = -1, r = INF;
			it = active[t[id]].lower_bound(mp(x[id], id+1));
			if (it != active[t[id]].end()) r = it->se;
			if (it != active[t[id]].begin()) {
				it--;
				l = it->se;
			}

			if (l == -1) st[1].update(r, -1);
			else if (r == INF) st[0].update(l, INF);
			else add(l, r);
		} else { //query
			int x = st[0].query_left(l[id], l[id]);
			int y = st[1].query_right(l[id], l[id]);
//			printf("x %d y %d\n", x, y);	
//			if (x != -1) cout << values[x].fi << " " << values[x].se << endl;
//			if (y != -1) cout << values[y].fi << " " << values[y].se << endl;
			if (x == -1 and y == -1) ans[id] = -1;
			else if (y == -1) ans[id] = l[id] - values[x].fi;
			else if (x == -1) ans[id] = values[y].fi - l[id];
			else ans[id] = max(values[y].fi -l[id], l[id] - values[x].fi);

			if (cnt != k) ans[id] = -1;
		}		
	}
	for (int i = 0; i < q; i++)
		printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:139:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < evt.size(); i++) {
                  ~~^~~~~~~~~~~~
new_home.cpp:138:6: warning: unused variable 'w' [-Wunused-variable]
  int w = 0;
      ^
new_home.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &k, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", x+i, t+i, a+i, b+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", l+i, y+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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