#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];
vector<int> flex[N];
int ans[N];
multiset<int> have[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]].pb(x[i]);
}
for (int i = 0; i < q; i++) {
pos[i] = upper_bound(all(coord), pos[i]) - coord.begin();
}
for (int i = 0; i < k; i++) {
sort(all(flex[i]));
}
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][0], flex[cur_type][0]);
update_min(1, 1, SZ(coord), flex[cur_type].back(), SZ(coord), flex[cur_type].back());
for (int pos = 0; pos + 1 < SZ(flex[cur_type]); pos++) {
int l = flex[cur_type][pos], r = flex[cur_type][pos + 1];
while (r - l > 1) {
int mid = (l + r) / 2;
if (coord[mid - 1] - coord[flex[cur_type][pos] - 1] <= coord[flex[cur_type][pos + 1] - 1] - coord[mid - 1]) {
l = mid;
}
else {
r = mid;
}
}
update_min(1, 1, SZ(coord), flex[cur_type][pos], l, flex[cur_type][pos]);
update_max(1, 1, SZ(coord), l + 1, flex[cur_type][pos + 1], flex[cur_type][pos + 1]);
}
}
for (int i = 0; i < q; i++) {
if (have_empty) {
cout << -1 << '\n';
continue;
}
int lpos = get_min(1, 1, SZ(coord), pos[i]), rpos = get_max(1, 1, SZ(coord), pos[i]);
int rez = 0;
if (lpos <= pos[i]) {
rez = max(rez, coord[pos[i] - 1] - coord[lpos - 1]);
}
if (rpos >= pos[i]) {
rez = max(rez, coord[rpos - 1] - coord[pos[i] - 1]);
}
cout << rez << '\n';
}
/*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]) {
for (int i = 0; i < k; i++) {
int rez = 1e9;
auto kek = have[i].upper_bound(it.F);
if (kek != have[i].end()) {
rez = min(rez, *kek - it.F);
}
if (kek != have[i].begin()) {
kek--;
rez = min(rez, it.F - *kek);
}
ans[it.S] = max(ans[it.S], rez);
}
}
for (auto it : del[cur_time]) {
have[it.S].erase(have[it.S].find(it.F));
}
}
for (int i = 0; i < q; i++) {
if (ans[i] == 1e9) {
cout << -1 << '\n';
}
else {
cout << ans[i] << '\n';
}
}*/
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:138:7: warning: unused variable 'max_time' [-Wunused-variable]
138 | int max_time = SZ(interesting);
| ^~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
42624 KB |
Output is correct |
2 |
Incorrect |
29 ms |
42744 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
42624 KB |
Output is correct |
2 |
Incorrect |
29 ms |
42744 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1288 ms |
86760 KB |
Output is correct |
2 |
Correct |
851 ms |
89020 KB |
Output is correct |
3 |
Correct |
1020 ms |
98168 KB |
Output is correct |
4 |
Correct |
1174 ms |
91908 KB |
Output is correct |
5 |
Correct |
881 ms |
89828 KB |
Output is correct |
6 |
Correct |
842 ms |
88980 KB |
Output is correct |
7 |
Correct |
939 ms |
98024 KB |
Output is correct |
8 |
Correct |
1216 ms |
91524 KB |
Output is correct |
9 |
Correct |
1144 ms |
91396 KB |
Output is correct |
10 |
Correct |
1027 ms |
90092 KB |
Output is correct |
11 |
Correct |
681 ms |
89080 KB |
Output is correct |
12 |
Correct |
845 ms |
90028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1244 ms |
86760 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
42624 KB |
Output is correct |
2 |
Incorrect |
29 ms |
42744 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
42624 KB |
Output is correct |
2 |
Incorrect |
29 ms |
42744 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |