Submission #1071778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071778		Tob	New Home (APIO18_new_home)	C++14	100 / 100	4342 ms	811916 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), inf = 2e9;

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

void walk(int x) {
	for (int ii = 0, o = 1; ii < 2; ii++, o = -o) {
		int cur = inf;
		for (auto it : ev[ii][x]) {
			int y = it.F;
			if (it.S) res[y] = max(res[y], o*h[y]-cur);
			else cur = min(cur, e[ii][y]*o);
		}
	}
	
	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]) if (sad != k) res[y] = -1;
	}
	else {
		walk(2*x);
		walk(2*x+1);
	}
}

void dodaj(int x, int a, int b, int o, pii y, int lo = 0, int hi = ofs-1) {
	if (b < lo || hi < a || a > b) return;
	if (a <= lo && hi <= b) {
		ev[o][x].pb(y);
		return;
	}
	int mid = (lo + hi) / 2;
	dodaj(2*x, a, b, o, y, lo, mid);
	dodaj(2*x+1, a, b, o, y, 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 nn2 = 1;
	for (int i = 0; i < n; i++) {
		cin >> g[i] >> ty[i] >> a[i] >> b[i]; b[i]++; ty[i]--;
		bb[nn2++] = a[i];
		bb[nn2++] = b[i];
	}
	for (int i = 0; i < q; i++) cin >> h[i] >> u[i];
	sort(bb, bb+nn2);
	int n2 = 1;
	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++) {u[i] = upper_bound(bb, bb+n2, u[i])-bb-1; qu[u[i]].pb(i);}
	
	int am = 0, bm = 0;
	vector <pair <pii, int> > va, vb;
	
	auto doo = [&](int x, int y, 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) {
			va.pb({{mid, 1}, am});
			gr[0][am] = {le[x], i-1};
			e[0][am++] = g[x];
		}
		if (y < n) {
			vb.pb({{mid1, 0}, bm});
			gr[1][bm] = {le[x], i-1};
			e[1][bm++] = g[y];
		}
	};
	
	g[n+1] = inf;
	for (int i = 0; i < k; i++) {
		s[i].insert({0, n+2*i});
		s[i].insert({(g[n+1] = inf), n+2*i+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, 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], i);
			le[x] = i;
		}
	}
	
	for (int i = 0; i < q; i++) {
		va.pb({{h[i], 0}, i});
		vb.pb({{h[i], 1}, i});
	}
	
	sort(all(va)); reverse(all(va));
	sort(all(vb));
	for (auto x : va) {
		if (x.F.S) dodaj(1, gr[0][x.S].F, gr[0][x.S].S, 0, {x.S, 0});
		else {
			int y = u[x.S]+ofs;
			while (y) {ev[0][y].pb({x.S, 1}); y /= 2;}
		}
	}
	for (auto x : vb) {
		if (!x.F.S) dodaj(1, gr[1][x.S].F, gr[1][x.S].S, 1, {x.S, 0});
		else {
			int y = u[x.S]+ofs;
			while (y) {ev[1][y].pb({x.S, 1}); y /= 2;}
		}
	}
	
	walk(1);
	
	for (int i = 0; i < q; i++) {
		cout << res[i] << "\n";
	}

	return 0;
}

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