oj.uz

Submission #545434

# Submission time Handle Problem Language Result Execution time Memory
545434 2022-04-04T14:06:15 Z valerikk New Home (APIO18_new_home) C++17
0 / 100
 1974 ms 113592 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int INF = 1e8;
const int N = 3e5 + 7;
 
struct Store {
	int x, t, a, b;
};
 
struct Query {
	int l, y;
};
 
int n, k, q;
Store st[N];
Query qq[N];
vector<int> ys;
vector<int> beg[N], en[N];
int m;
int ans[N];
set<pair<int, int>> s[N];
int mn[2 * N];
 
void upd(int l, int r, int x) {
	l += m, r += m;
	while (l < r) {
		if (l & 1) {
			mn[l] = min(mn[l], x);
			++l;
		}
		if (r & 1) {
			--r;
			mn[r] = min(mn[r], x);
		}
		l >>= 1, r >>= 1;
	}
}
 
int get(int i) {
	i += m;
	int res = INF + 1;
	for (; i > 0; i >>= 1) {
		res = min(res, mn[i]);
	}
	return res;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k >> q;
	for (int i = 0; i < n; ++i) {
		auto &[x, t, a, b] = st[i];
		cin >> x >> t >> a >> b;
	}
	for (int i = 0; i < q; ++i) {
		auto &[l, y] = qq[i];
		cin >> l >> y;
		ys.push_back(y);
	}
 
	sort(ys.begin(), ys.end());
	ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
	m = ys.size();
 
	for (int i = 0; i < n; ++i) {
		st[i].a = lower_bound(ys.begin(), ys.end(), st[i].a) - ys.begin();
		st[i].b = lower_bound(ys.begin(), ys.end(), st[i].b + 1) - ys.begin();
		--st[i].t;
	}
	for (int i = 0; i < q; ++i) {
		qq[i].y = lower_bound(ys.begin(), ys.end(), qq[i].y) - ys.begin();
	}
 
	for (int i = 0; i < n; ++i) {
		beg[st[i].a].push_back(i);
		en[st[i].b].push_back(i);
	}
 
	for (int _ = 0; _ < 2; ++_) {
		for (int i = 0; i < k; ++i) {
			s[i].clear();
			s[i].insert({0, -1});
			s[i].insert({INF + 1, -1});
		}
		vector<pair<pair<int, int>, pair<int, int>>> v;
		auto kek = [&](int x1, int x2, int y, int type) {
			if (x1 == 0) return;
			if (x1 < x2) {
				if (x2 != INF + 1) {
					x2 = (x1 + x2) / 2 + 1;
				}
				v.push_back({{x1, x2}, {y, type}});
			}
		};
 
		for (int i = 0; i <= m; ++i) {
			for (int id : beg[i]) {
				auto [it, fl] = s[st[id].t].insert({st[id].x, id});
				assert(fl);
				kek(prev(it)->first, st[id].x, i, 1);
				kek(st[id].x, next(it)->first, i, 1);
				kek(prev(it)->first, next(it)->first, i, -1);
			}
			for (int id : en[i]) {
				auto it = s[st[id].t].find({st[id].x, id});
				kek(prev(it)->first, st[id].x, i, -1);
				kek(st[id].x, next(it)->first, i, -1);
				kek(prev(it)->first, next(it)->first, i, 1);
				s[st[id].t].erase(it);
			}
			// cout << "Time: " << i << endl;
			// for (auto z : s[0]) {
			// 	cout << z.first << " ";
			// }
			// cout << endl;
		}
 	
 		sort(v.begin(), v.end(), [&](const auto &p1, const auto &p2) {
 			return p1.first.second > p2.first.second || (p1.first.second == p2.first.second && p1.second < p2.second);
 		});

		vector<int> qord(q);
		iota(qord.begin(), qord.end(), 0);
		sort(qord.begin(), qord.end(), [&](const int &i, const int &j) {
			return qq[i].l > qq[j].l;
		});
 
		for (int i = 0; i < 2 * m; ++i) {
			mn[i] = INF;
		}
 
		int ptr = 0;
		for (int i = 0; i < q; ++i) {
			while (ptr < (int)v.size() && v[ptr].first.second > qq[qord[i]].l) {
				int pp = ptr;
				vector<pair<int, int>> cur;
				while (ptr < (int)v.size() && v[ptr].first == v[pp].first) {
					cur.push_back(v[ptr].second);
					++ptr;
				}
				int bal = 0;
				for (int j = 0; j < (int)cur.size(); ++j) {
					bal += cur[j].second;
					if (bal > 0) {
						upd(cur[j].first, j == (int)cur.size() - 1 ? m : cur[j + 1].first, v[pp].first.first);
					}
				}
			}
			ans[qord[i]] = max(ans[qord[i]], qq[qord[i]].l - get(qq[qord[i]].y));
		}
 
 
		for (int i = 0; i < n; ++i) {
			st[i].x = INF - st[i].x + 1;
		}
		for (int i = 0; i < q; ++i) {
			qq[i].l = INF - qq[i].l + 1;
		}
	}
 
	vector<int> cnt(k, 0);
	vector<bool> good(m + 1);
	int z = k;
	for (int i = 0; i <= m; ++i) {
		for (int id : beg[i]) {
			z -= cnt[st[id].t] == 0;
			++cnt[st[id].t];
			z += cnt[st[id].t] == 0;
		}
		for (int id : en[i]) {
			z -= cnt[st[id].t] == 0;
			--cnt[st[id].t];
			z += cnt[st[id].t] == 0;
		}
		good[i] = z == 0;
	}
	for (int i = 0; i < q; ++i) {
		if (!good[qq[i].y]) {
			cout << "-1\n";
		} else {
			cout << ans[i] << "\n";
		}
	}
 
 
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28516 KB Output is correct
2 Correct 15 ms 28500 KB Output is correct
3 Correct 14 ms 28472 KB Output is correct
4 Incorrect 16 ms 28452 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28516 KB Output is correct
2 Correct 15 ms 28500 KB Output is correct
3 Correct 14 ms 28472 KB Output is correct
4 Incorrect 16 ms 28452 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1272 ms 105632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1974 ms 113592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28516 KB Output is correct
2 Correct 15 ms 28500 KB Output is correct
3 Correct 14 ms 28472 KB Output is correct
4 Incorrect 16 ms 28452 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28516 KB Output is correct
2 Correct 15 ms 28500 KB Output is correct
3 Correct 14 ms 28472 KB Output is correct
4 Incorrect 16 ms 28452 KB Output isn't correct
5 Halted 0 ms 0 KB -