Submission #545331

#	Time	Username	Problem	Language	Result	Execution time	Memory
545331		valerikk	New Home (APIO18_new_home)	C++17	0 / 100	1090 ms	508912 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

const int N = 300228;
const int INF = 4e8 + 7;
const int OPEN = 0;
const int CLOSE = 1;
const int M = 1000228;

struct Store {
	int x, t, a, b;
};

struct Query {
	int l, y;
};

struct Event {
	int x;
	int type;
	int id;

	bool operator<(const Event &other) {
		return x < other.x;
	}
};

int n, k, q;
Store s[N];
Query qq[N];
int qord[N];
Event ev[2 * N];

multiset<int> S[N];
vector<int> xs;
multiset<int> treeL[2 * M], treeR[2 * M];

int qans[N];

int getInd(int x) {
	return (int)(lower_bound(xs.begin(), xs.end(), x) - xs.begin());
}

void fadds(int l, int r) {
	if (l < r) {
		xs.push_back(l);
		xs.push_back((l + r + 1) / 2);
		xs.push_back(r + 1);
	}
}

void fadd(int t, int x) {
	auto it = S[t].insert(x);
	fadds(*prev(it), x);
	fadds(x, *next(it));
}

void fremove(int t, int x) {
	auto it = S[t].find(x);
	fadds(*prev(it), *next(it));
	S[t].erase(it);
}

void addL(int l, int r, int L) {
	l += M, r += M;
	while (l < r) {
		if (l & 1) {
			treeL[l].insert(L);
			++l;
		}
		if (r & 1) {
			--r;
			treeL[r].insert(L);
		}
		l >>= 1, r >>= 1;
	}
}

void removeL(int l, int r, int L) {
	l += M, r += M;
	while (l < r) {
		if (l & 1) {
			treeL[l].erase(treeL[l].find(L));
			++l;
		}
		if (r & 1) {
			--r;
			treeL[r].erase(treeL[r].find(L));
		}
		l >>= 1, r >>= 1;
	}
}

void addR(int l, int r, int R) {
	l += M, r += M;
	while (l < r) {
		if (l & 1) {
			treeR[l].insert(R);
			++l;
		}
		if (r & 1) {
			--r;
			treeR[r].insert(R);
		}
		l >>= 1, r >>= 1;
	}
}

void removeR(int l, int r, int R) {
	l += M, r += M;
	while (l < r) {
		if (l & 1) {
			treeR[l].erase(treeR[l].find(R));
			++l;
		}
		if (r & 1) {
			--r;
			treeR[r].erase(treeR[r].find(R));
		}
		l >>= 1, r >>= 1;
	}
}

void adds(int l, int r) {
	if (l < r) {
		addL(getInd(l), getInd((l + r + 1) / 2), l);
		addR(getInd((l + r + 1) / 2), getInd(r + 1), r);
	}
}

void removes(int l, int r) {
	if (l < r) {
		removeL(getInd(l), getInd((l + r + 1) / 2), l);
		removeR(getInd((l + r + 1) / 2), getInd(r + 1), r);
	}
}

void add(int t, int x) {
	auto it = S[t].insert(x);
	removes(*prev(it), *next(it));
	adds(*prev(it), x);
	adds(x, *next(it));
}

void remove(int t, int x) {
	auto it = S[t].find(x);
	assert(it != S[t].end());
	removes(*prev(it), x);
	removes(x, *next(it));
	adds(*prev(it), *next(it));
	S[t].erase(it);
}

int getL(int x) {
	int mn = INF;
	for (int v = getInd(x) - 1 + M; v > 0; v >>= 1) {
		if (!treeL[v].empty()) {
			mn = min(mn, *treeL[v].begin());
		}
	}
	return mn;
}

int getR(int x) {
	int mx = 0;
	for (int v = getInd(x) - 1 + M; v > 0; v >>= 1) {
		if (!treeR[v].empty()) {
			mx = max(mx, *treeR[v].rbegin());
		}
	}
	return mx;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> k >> q;
	for (int i = 0; i < n; ++i) {
		cin >> s[i].x >> s[i].t >> s[i].a >> s[i].b;
		s[i].x += (int)1e8 + 10;
	}
	for (int i = 0; i < q; ++i) {
		cin >> qq[i].l >> qq[i].y;
		qq[i].l += (int)1e8 + 10;
	}

	for (int i = 0; i < n; ++i) {
		++s[i].b;
		--s[i].t;
	}

	for (int i = 0; i < n; ++i) {
		ev[2 * i] = {s[i].a, OPEN, i};
		ev[2 * i + 1] = {s[i].b, CLOSE, i};
	}
	sort(ev, ev + 2 * n);

	for (int i = 0; i < q; ++i) {
		qord[i] = i;
	}
	sort(qord, qord + q, [&](const int &i, const int &j) {
		return qq[i].y < qq[j].y;
	});

	xs.push_back(0);
	xs.push_back(INF + 1);
	xs.push_back((0 + INF + 1) / 2);
	for (int i = 0; i < k; ++i) {
		S[i].insert(0);
		S[i].insert(INF);
	}

	int ptr = 0;
	for (int i = 0; i < q; ++i) {
		while (ptr < 2 * n && ev[ptr].x <= qq[qord[i]].y) {
			auto E = ev[ptr];
			if (E.type == OPEN) {
				fadd(s[E.id].t, s[E.id].x);
			} else {
				fremove(s[E.id].t, s[E.id].x);
			}
			++ptr;
		}
	}

	sort(xs.begin(), xs.end());
	xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
	assert(xs.size() < M);

	for (int i = 0; i < k; ++i) {
		S[i].clear();
		S[i].insert(0);
		S[i].insert(INF);
		adds(0, INF);
	}

	ptr = 0;
	for (int i = 0; i < q; ++i) {
		while (ptr < 2 * n && ev[ptr].x <= qq[qord[i]].y) {
			auto E = ev[ptr];
			if (E.type == OPEN) {
				add(s[E.id].t, s[E.id].x);
			} else {
				remove(s[E.id].t, s[E.id].x);
			}
			++ptr;
		}

		int L = getL(qq[qord[i]].l);
		int R = getR(qq[qord[i]].l);
		if (L == 0 || R == INF) {
			qans[qord[i]] = -1;
		} else {
			qans[qord[i]] = max(qq[qord[i]].l - L, R - qq[qord[i]].l);
		}
	}

	for (int i = 0; i < q; ++i) {
		cout << qans[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