Submission #1070899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070899		Tob	New Home (APIO18_new_home)	C++14	0 / 100	5041 ms	597932 KiB

new_home

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int N = 3e5 + 7, ofs = (1 << 20), C = 5e7, inf = 2e9;

int n, k, q, cnt, cur, sad;
int a[N], b[N], g[N], ty[N], h[N], u[N], aa[N], bb[2*N], res[N], bl[4*N], fr[N], le[2*N];
int t[2][2*ofs], ch[C][2];
vector <int> qu[ofs], addk[ofs], remk[ofs], dod[2*N], rem[2*N];
set <pii> s[N];

struct node {
	int l, r, d, type;
};

vector <node> ad[2*ofs];

void change(int x, int o, int val) {
	ch[cnt][0] = 2*x+o;
	ch[cnt][1] = t[o][x];
	t[o][x] = val;
	cnt++;
}

int add(int x, int a, int b, int o, int val, int lo = 0, int hi = ofs-1) {
	if (b < lo || hi < a) return 0;
	int mid = (lo + hi) / 2, ha = o*((hi-lo)/2+1);
	if (a <= lo && hi <= b) {
		if (t[o][x] >= val) {
			change(x, o, val);
			return 0;
		}
		if (lo == hi) return 1;
		if (add(2*x^o^1, a, b, o, val, mid+1-ha, hi-ha)) return 1;
		add(2*x^o, a, b, o, val, lo+ha, mid+ha);
		return 1;
	}
	if (add(2*x^o^1, a, b, o, val, mid+1-ha, hi-ha)) return 1;
	if (add(2*x^o, a, b, o, val, lo+ha, mid+ha)) return 1;
	change(x, o, min(t[o][2*x], t[o][2*x+1]));
	return 0;
}

int query(int x, int a, int o, int val = -inf, int lo = 0, int hi = ofs-1) {
	if (t[o][x] != inf) val = max(val, t[o][x]);
	if (lo == hi) return val;
	int mid = (lo + hi) / 2;
	if (a <= mid) return query(2*x, a, o, val, lo, mid);
	return query(2*x+1, a, o, val, mid+1, hi);
}

void walk(int x) {
	for (auto it : ad[x]) {
		int ccnt = cnt;
		if (it.l <= it.r) add(1, it.l, it.r, it.type, it.d);
		ccnt = cnt-ccnt;
		bl[cur++] = ccnt;
	}
	if (x-ofs > 2*n);
	else if (x >= ofs) {
		for (auto y : addk[x-ofs]) {fr[y]++; sad += (fr[y] == 1);}
		for (auto y : remk[x-ofs]) {fr[y]--; sad -= (!fr[y]);}
		for (auto y : qu[x-ofs]) {
			int pos = aa[h[y]];
			if (sad != k) res[y] = -1;
			else res[y] = max(pos-query(1, h[y], 0), -query(1, h[y], 1)-pos);
		}
	}
	else {
		walk(2*x);
		walk(2*x+1);
	}
	for (int i = ad[x].size(); i; i--, cur--) 
		for (int j = 0; j < bl[cur-1]; j++, cnt--) 
			t[ch[cnt-1][0]&1][ch[cnt-1][0]>>1] = ch[cnt-1][1];
}

void dodaj(int x, int a, int b, node nn, int lo = 0, int hi = ofs-1) {
	if (b < lo || hi < a || a > b) return;
	if (a <= lo && hi <= b) {
		ad[x].pb(nn);
		return;
	}
	int mid = (lo + hi) / 2;
	dodaj(2*x, a, b, nn, lo, mid);
	dodaj(2*x+1, a, b, nn, mid+1, hi);
}

int main () {
	FIO;
	for (int i = 0; i < 2; i++) for (int j = 0; j < 2*ofs; j++) t[i][j] = inf;
	
	cin >> n >> k >> q;
	
	int nn1 = 1, nn2 = 1;
	for (int i = 0; i < n; i++) {
		cin >> g[i] >> ty[i] >> a[i] >> b[i]; b[i]++; ty[i]--;
		aa[nn1++] = g[i];
		bb[nn2++] = a[i];
		bb[nn2++] = b[i];
	}
	for (int i = 0; i < q; i++) {
		cin >> h[i] >> u[i];
		aa[nn1++] = h[i];
	}
	sort(aa, aa+nn1);
	sort(bb, bb+nn2);
	int n1 = 1, n2 = 1;
	for (int i = 1; i < nn1; i++) if (aa[i] != aa[n1-1]) aa[n1++] = aa[i];
	for (int i = 1; i < nn2; i++) if (bb[i] != bb[n2-1]) bb[n2++] = bb[i];
	for (int i = 0; i < n; i++) {
		a[i] = upper_bound(bb, bb+n2, a[i])-bb-1;
		b[i] = upper_bound(bb, bb+n2, b[i])-bb-1;
		dod[a[i]].pb(i);
		rem[b[i]].pb(i);
		addk[a[i]].pb(ty[i]);
		remk[b[i]].pb(ty[i]);
	}
	for (int i = 0; i < q; i++) {
		h[i] = upper_bound(aa, aa+n1, h[i])-aa-1;
		u[i] = upper_bound(bb, bb+n2, u[i])-bb-1;
		qu[u[i]].pb(i);
	}
	
	auto doo = [&](int x, int y, int z, int i) {
		int mid = (y < n) ? (g[x]+g[y])/2 : inf, mid1 = (x < n) ? (g[x]+g[y]+1)/2 : 0;
		if (x < n) {
			mid = upper_bound(aa, aa+n1, mid)-aa-1;
			node na = {0, mid, g[x], 0};
			dodaj(1, le[x], i-1, na);
		}
		if (y < n) {
			mid1 = lower_bound(aa, aa+n1, mid1)-aa;
			node nb = {mid1, ofs-1, -g[y], 1};
			dodaj(1, le[x], i-1, nb);
		}
	};
	
	g[n+1] = inf;
	for (int i = 0; i < k; i++) {
		s[i].insert({0, n});
		s[i].insert({(g[n+1] = inf), n+1});
	}
	for (int i = 0; i < n2; i++) {
		for (auto it : dod[i]) {
			auto p = s[ty[it]].lower_bound({g[it], it});
			int y = p->S; --p; int x = p->S;
			doo(x, y, it, i);
			le[x] = le[it] = i;
			s[ty[it]].insert({g[it], it});
		}
		for (auto it : rem[i]) {
			s[ty[it]].erase({g[it], it});
			auto p = s[ty[it]].lower_bound({g[it], it});
			int y = p->S; --p; int x = p->S;
			int ob[2][2] = {{x, it}, {it, y}};
			for (int j = 0; j < 2; j++) doo(ob[j][0], ob[j][1], it, i);
			le[x] = i;
		}
	}
	
	walk(1);
	
	for (int i = 0; i < q; i++) {
		cout << res[i] << "\n";
	}

	return 0;
}

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