#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
//#define int ll
const int N = 3e5 + 10;
vector<pair<int, int>> add[N], del[N], que[N];
multiset<int> flex[N];
int ans[N];
const int M = 5e6 + 10;
int mn[M], mx[M];
void build_min(int v, int l, int r) {
mn[v] = 1e9;
if (l == r) {
return;
}
int mid = (l + r) / 2;
build_min(2 * v, l, mid);
build_min(2 * v + 1, mid + 1, r);
}
void build_max(int v, int l, int r) {
mx[v] = 0;
if (l == r) {
return;
}
int mid = (l + r) / 2;
build_max(2 * v, l, mid);
build_max(2 * v + 1, mid + 1, r);
}
void update_min(int v, int l, int r, int a, int b, int vl) {
if (l > b || r < a) {
return;
}
if (l >= a && r <= b) {
mn[v] = min(mn[v], vl);
return;
}
int mid = (l + r) / 2;
update_min(2 * v, l, mid, a, b, vl);
update_min(2 * v + 1, mid + 1, r, a, b, vl);
}
void update_max(int v, int l, int r, int a, int b, int vl) {
if (l > b || r < a) {
return;
}
if (l >= a && r <= b) {
mx[v] = max(mx[v], vl);
return;
}
int mid = (l + r) / 2;
update_max(2 * v, l, mid, a, b, vl);
update_max(2 * v + 1, mid + 1, r, a, b, vl);
}
int get_min(int v, int l, int r, int need) {
if (l == r) {
return mn[v];
}
int mid = (l + r) / 2;
if (need <= mid) {
return min(mn[v], get_min(2 * v, l, mid, need));
}
return min(mn[v], get_min(2 * v + 1, mid + 1, r, need));
}
int get_max(int v, int l, int r, int need) {
if (l == r) {
return mx[v];
}
int mid = (l + r) / 2;
if (need <= mid) {
return max(mx[v], get_max(2 * v, l, mid, need));
}
return max(mx[v], get_max(2 * v + 1, mid + 1, r, need));
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k, q;
cin >> n >> k >> q;
vector<int> x(n), type(n), l(n), r(n), interesting, coord;
for (int i = 0; i < n; i++) {
cin >> x[i] >> type[i] >> l[i] >> r[i];
interesting.pb(l[i]);
interesting.pb(r[i]);
coord.pb(x[i]);
type[i]--;
}
vector<int> pos(q), tt(q);
for (int i = 0; i < q; i++) {
cin >> pos[i] >> tt[i];
interesting.pb(tt[i]);
coord.pb(pos[i]);
}
sort(all(coord));
coord.resize(unique(all(coord)) - coord.begin());
for (int &x : coord) {
cerr << x << ' ';
}
cerr << '\n';
build_min(1, 1, SZ(coord));
build_max(1, 1, SZ(coord));
for (int i = 0; i < n; i++) {
x[i] = upper_bound(all(coord), x[i]) - coord.begin();
flex[type[i]].insert(x[i]);
}
for (int i = 0; i < q; i++) {
pos[i] = upper_bound(all(coord), pos[i]) - coord.begin();
}
sort(all(interesting));
interesting.resize(unique(all(interesting)) - interesting.begin());
for (int i = 0; i < n; i++) {
l[i] = upper_bound(all(interesting), l[i]) - interesting.begin();
r[i] = upper_bound(all(interesting), r[i]) - interesting.begin();
}
for (int i = 0; i < q; i++) {
tt[i] = upper_bound(all(interesting), tt[i]) - interesting.begin();
}
int max_time = SZ(interesting);
bool have_empty = false;
for (int cur_type = 0; cur_type < k; cur_type++) {
if (flex[cur_type].empty()) {
have_empty = true;
break;
}
update_max(1, 1, SZ(coord), 1, *flex[cur_type].begin(), *flex[cur_type].begin());
update_min(1, 1, SZ(coord), *flex[cur_type].rbegin(), SZ(coord), *flex[cur_type].rbegin());
auto it = flex[cur_type].begin();
for (int pos = 0; pos + 1 < SZ(flex[cur_type]); pos++) {
auto it2 = it;
it2++;
if (it2 == flex[cur_type].end()) {
break;
}
int l = *it, r = *it2;
while (r - l > 1) {
int mid = (l + r) / 2;
if (coord[mid - 1] - coord[*it - 1] <= coord[*it2 - 1] - coord[mid - 1]) {
l = mid;
}
else {
r = mid;
}
}
update_min(1, 1, SZ(coord), *it, l, *it);
update_max(1, 1, SZ(coord), r, *it2, *it2);
it++;
}
}
exit(0);
for (int i = 0; i < n; i++) {
//add[l[i]].pb({x[i], type[i]});
del[r[i]].pb({x[i], type[i]});
}
for (int i = 0; i < q; i++) {
que[tt[i]].pb({pos[i], i});
}
for (int cur_time = 1; cur_time <= max_time; cur_time++) {
/*for (auto it : add[cur_time]) {
have[it.S].insert(it.F);
}*/
for (auto it : que[cur_time]) {
if (have_empty) {
ans[it.S] = 1e9;
continue;
}
int lpos = get_min(1, 1, SZ(coord), it.F), rpos = get_max(1, 1, SZ(coord), it.F);
if (lpos <= it.F) {
ans[it.S] = max(ans[it.S], coord[it.F - 1] - coord[lpos - 1]);
}
if (rpos >= it.F) {
ans[it.S] = max(ans[it.S], coord[rpos - 1] - coord[it.F - 1]);
}
}
for (auto cpar : del[cur_time]) {
if (have_empty) {
break;
}
flex[cpar.S].erase(flex[cpar.S].find(cpar.F));
if (flex[cpar.S].find(cpar.F) != flex[cpar.S].end()) {
continue;
}
if (flex[cpar.S].empty()) {
have_empty = true;
break;
}
auto it2 = flex[cpar.S].upper_bound(cpar.F);
if (it2 == flex[cpar.S].end()) {
update_min(1, 1, SZ(coord), *flex[cpar.S].rbegin(), SZ(coord), *flex[cpar.S].rbegin());
}
else if (it2 == flex[cpar.S].begin()) {
update_max(1, 1, SZ(coord), 1, *flex[cpar.S].begin(), *flex[cpar.S].begin());
}
else {
auto it = it2;
it--;
int l = *it, r = *it2;
while (r - l > 1) {
int mid = (l + r) / 2;
if (coord[mid - 1] - coord[*it - 1] <= coord[*it2 - 1] - coord[mid - 1]) {
l = mid;
}
else {
r = mid;
}
}
update_min(1, 1, SZ(coord), *it, l, *it);
update_max(1, 1, SZ(coord), l + 1, *it2, *it2);
}
}
}
for (int i = 0; i < q; i++) {
if (ans[i] == 1e9) {
cout << -1 << '\n';
}
else {
cout << ans[i] << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
35584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
35584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3834 ms |
84612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4019 ms |
84360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
35584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
35584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
