This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 600000000
#define MOD 1000000007
#define MAX_N (1<<19)
inline int dist(const multiset<int> &s, int d) {
if (s.empty()) return 0;
else return max(abs(d-*s.begin()), abs(d-*s.rbegin()));
}
struct SegTree {
multiset<int> seg[MAX_N*2-1];
void add(int a, int b, int x, int k=0, int l=0, int r=MAX_N) {
if (b <= l || r <= a) return;
if (a <= l && r <= b) {
seg[k].insert(x);
return;
}
add(a, b, x, k*2+1, l, (l+r)/2);
add(a, b, x, k*2+2, (l+r)/2, r);
}
void remove(int a, int b, int x, int k=0, int l=0, int r=MAX_N) {
if (b <= l || r <= a) return;
if (a <= l && r <= b) {
auto it = seg[k].find(x);
assert(it != seg[k].end());
seg[k].erase(it);
return;
}
remove(a, b, x, k*2+1, l, (l+r)/2);
remove(a, b, x, k*2+2, (l+r)/2, r);
}
int query(int k, int x) {
k += MAX_N-1;
int m = dist(seg[k], x);
while (k > 0) {
k = (k-1)/2;
m = max(m, dist(seg[k], x));
}
return m;
}
} seg;
int N, K, Q;
int T[300000], A[300000], B[300000];
int L[300000], Y[300000];
#define MAX_Y 300000
vector<int> Gopen[MAX_Y];
vector<int> Gclose[MAX_Y];
vector<int> Gquery[MAX_Y];
#define MAX_X 300000
int X[MAX_X];
int rangeL[MAX_X], rangeR[MAX_X];
int ans[300000];
vector<int> years, xs;
void addRange(int id) {
int l = lower_bound(all(xs), rangeL[id]) - xs.begin();
int r = upper_bound(all(xs), rangeR[id]) - xs.begin() - 1;
if (l > r) return;
seg.add(l, r+1, X[id]);
}
void removeRange(int id) {
int l = lower_bound(all(xs), rangeL[id]) - xs.begin();
int r = upper_bound(all(xs), rangeR[id]) - xs.begin() - 1;
if (l > r) return;
seg.remove(l, r+1, X[id]);
}
set<P> kind[300000]; // (pos, i)
void add(int k, P val) {
int x = val._2;
auto it = kind[k].lower_bound(val);
assert(it != kind[k].end() && it != kind[k].begin());
int b = (*it)._2;
int a = (*(--it))._2;
kind[k].insert(val);
removeRange(a);
removeRange(b);
rangeR[a] = rangeL[x] = (X[a]+X[x])/2;
rangeR[x] = rangeL[b] = (X[b]+X[x])/2;
addRange(a);
addRange(b);
addRange(x);
}
void remove(int k, P val) {
int x = val._2;
kind[k].erase(val);
auto it = kind[k].lower_bound(val);
assert(it != kind[k].end() && it != kind[k].begin());
int b = (*it)._2;
int a = (*(--it))._2;
removeRange(a);
removeRange(b);
removeRange(x);
rangeR[a] = rangeL[b] = (X[a]+X[b])/2;
addRange(a);
addRange(b);
}
int maxDist(int pos) {
int x = index(xs, pos);
return seg.query(x, pos);
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> N >> K >> Q;
rep(i, N) {
cin >> X[i] >> T[i] >> A[i] >> B[i];
X[i] *= 2;
T[i]--;
}
rep(i, Q) {
cin >> L[i] >> Y[i];
L[i] *= 2;
xs.pb(L[i]);
years.pb(Y[i]);
}
sort(all(years)); uniq(years);
assert(years.size() <= MAX_Y);
rep(i, N) Gopen[index(years, A[i])].pb(i);
rep(i, N) Gclose[index(years, B[i]+1)].pb(i);
rep(i, Q) Gquery[index(years, Y[i])].pb(i);
rep(i, Q) ans[i] = -2;
sort(all(xs)); uniq(xs);
assert(xs.size() <= MAX_X);
rep(k, K) {
int id1 = N+2*k, id2 = N+2*k+1;
X[id1] = -INF;
kind[k].insert(P(-INF, id1));
rangeL[id1] = -INF;
rangeR[id1] = 0;
addRange(id1);
X[id2] = +INF;
kind[k].insert(P(+INF, id2));
rangeL[id2] = 0;
rangeR[id2] = +INF;
addRange(id2);
}
rep(y, years.size()) {
for (int i : Gopen[y]) add(T[i], P(X[i], i));
for (int i : Gclose[y]) remove(T[i], P(X[i], i));
for (int q : Gquery[y]) {
int m = maxDist(L[q])/2;
if (m > 1e8) m = -1;
ans[q] = m;
}
}
rep(i, Q) cout << ans[i] << "\n";
return 0;
}
Compilation message (stderr)
new_home.cpp: In function 'int main()':
new_home.cpp:17:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i, n) for (int i=0; i<(n); i++)
^
new_home.cpp:172:3: note: in expansion of macro 'rep'
rep(y, years.size()) {
^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |