#include <set>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1012345678;
class segment {
public:
int l, r, x;
segment() : l(0), r(0), x(0) {};
segment(int l_, int r_, int x_) : l(l_), r(r_), x(x_) {};
bool operator<(const segment& s) const {
if(l != s.l) return l < s.l;
if(r != s.r) return r < s.r;
return x < s.x;
}
};
class query {
public:
int l, r, x, w;
query() : l(0), r(0), x(0), w(0) {};
query(int l_, int r_, int x_, int w_) : l(l_), r(r_), x(x_), w(w_) {};
bool operator<(const query& q) const {
if(x != q.x) return x < q.x;
return w < q.w;
}
};
class segtree {
private:
int sz;
vector<int> val;
public:
segtree() : sz(0), val(vector<int>()) {};
segtree(int sz_) {
sz = 1;
while(sz < sz_) sz *= 2;
val = vector<int>(sz * 2, -inf);
}
void update(int l, int r, int x) {
l += sz;
r += sz;
while(l != r) {
if(l & 1) val[l] = max(val[l], x), ++l;
if(r & 1) --r, val[r] = max(val[r], x);
l >>= 1, r >>= 1;
}
}
int get(int pos) {
pos += sz;
int ans = -inf;
while(pos >= 1) {
ans = max(ans, val[pos]);
pos >>= 1;
}
return ans;
}
};
vector<int> solve(int N, int K, int Q, vector<int> X, vector<int> T, vector<int> A, vector<int> B, vector<int> L, vector<int> Y) {
vector<int> comp = { 0, inf };
vector<vector<int> > G(K);
for(int i = 0; i < N; ++i) {
++B[i], --T[i];
comp.push_back(A[i]);
comp.push_back(B[i]);
X[i] *= 2;
G[T[i]].push_back(i);
}
for(int i = 0; i < Q; ++i) {
L[i] *= 2;
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
int S = comp.size();
for(int i = 0; i < N; ++i) {
A[i] = lower_bound(comp.begin(), comp.end(), A[i]) - comp.begin();
B[i] = lower_bound(comp.begin(), comp.end(), B[i]) - comp.begin();
}
for(int i = 0; i < Q; ++i) {
Y[i] = lower_bound(comp.begin(), comp.end(), Y[i] + 1) - comp.begin() - 1;
}
vector<query> qs;
for(int i = 0; i < K; ++i) {
set<segment> st;
st.insert(segment(0, S, -inf));
vector<segment> iniqs;
for(int j : G[i]) {
iniqs.push_back(segment(A[j], B[j], X[j]));
}
sort(iniqs.begin(), iniqs.end(), [](segment s1, segment s2) { return s1.x < s2.x; });
for(segment s : iniqs) {
set<segment>::iterator it = st.lower_bound(segment(s.l, s.r, s.x));
if(it != st.begin()) --it;
set<segment> nst;
while(it != st.end() && it->l < s.r) {
segment t = *it;
it = st.erase(it);
int al = max(t.l, s.l), ar = min(t.r, s.r);
if(al >= ar) continue;
qs.push_back(query(al, ar, (s.x + t.x) / 2, (s.x - t.x) / 2));
nst.insert(segment(al, ar, s.x));
if(t.l < al) nst.insert(segment(t.l, al, t.x));
if(ar < t.r) nst.insert(segment(ar, t.r, t.x));
}
st.insert(nst.begin(), nst.end());
}
for(segment s : st) {
qs.push_back(query(s.l, s.r, (inf + s.x) / 2, (inf - s.x) / 2));
}
}
for(int i = 0; i < Q; ++i) {
qs.push_back(query(Y[i], Y[i] + 1, L[i], -(i + 1)));
}
sort(qs.begin(), qs.end());
segtree seg(S);
for(query i : qs) {
if(i.w >= 0 && i.x - i.w == -inf) {
seg.update(i.l, i.r, i.x + i.w);
}
}
vector<int> ans(Q, -1);
for(query i : qs) {
if(i.w < 0) {
ans[-i.w - 1] = max(ans[-i.w - 1], seg.get(i.l) - i.x);
}
else {
seg.update(i.l, i.r, i.x + i.w);
}
}
reverse(qs.begin(), qs.end());
seg = segtree(S);
for(query i : qs) {
if(i.w >= 0 && i.x + i.w == inf) {
seg.update(i.l, i.r, -(i.x - i.w));
}
}
for(query i : qs) {
if(i.w < 0) {
ans[-i.w - 1] = max(ans[-i.w - 1], i.x - (-seg.get(i.l)));
}
else {
seg.update(i.l, i.r, -(i.x - i.w));
}
}
for(int i = 0; i < Q; ++i) {
if(ans[i] > inf / 3) ans[i] = -1;
}
return ans;
}
vector<int> solve_easy(int N, int K, int Q, vector<int> X, vector<int> T, vector<int> A, vector<int> B, vector<int> L, vector<int> Y) {
for(int i = 0; i < N; ++i) {
--T[i];
}
vector<int> ans(Q);
for(int i = 0; i < Q; ++i) {
vector<int> sub(K, inf);
for(int j = 0; j < N; ++j) {
if(A[j] <= Y[i] && Y[i] <= B[j]) {
sub[T[j]] = min(sub[T[j]], abs(X[j] - L[i]));
}
}
ans[i] = *max_element(ans.begin(), ans.end());
if(ans[i] > inf / 3) ans[i] = -1;
}
return ans;
}
#include <random>
mt19937 mt(1905162106);
int rand_rng(int l, int r) {
uniform_int_distribution<int> p(l, r - 1);
return p(mt);
}
void random_gen() {
int N = 10, K = 10, Q = 10;
for(int rep = 1; rep <= 1000; ++rep) {
vector<int> X(N), T(N), A(N), B(N), L(Q), Y(Q);
for(int i = 0; i < N; ++i) {
X[i] = rand_rng(0, 100000000);
T[i] = rand_rng(1, K + 1);
A[i] = rand_rng(0, 100000000);
B[i] = rand_rng(0, 100000000);
if(A[i] > B[i]) swap(A[i], B[i]);
}
for(int i = 0; i < Q; ++i) {
L[i] = rand_rng(0, 100000000);
Y[i] = rand_rng(0, 100000000);
}
vector<int> res1 = solve(N, K, Q, X, T, A, B, L, Y);
vector<int> res2 = solve_easy(N, K, Q, X, T, A, B, L, Y);
if(res1 != res2) {
cout << "Case #" << rep << ": " << endl;
cout << "N = " << N << ", K = " << K << ", Q = " << Q << endl;
for(int i = 0; i < N; ++i) {
cout << "(" << X[i] << ", " << T[i] << ", " << A[i] << ", " << B[i] << ")" << endl;
}
cout << "[";
for(int i = 0; i < Q; ++i) {
if(i) cout << ", ";
cout << "(" << L[i] << ", " << Y[i] << ")";
}
cout << "]" << endl;
cout << "Returns: [";
for(int i = 0; i < Q; ++i) {
if(i) cout << ", ";
cout << res1[i];
}
cout << "]" << endl;
cout << "Answer: [";
for(int i = 0; i < Q; ++i) {
if(i) cout << ", ";
cout << res2[i];
}
cout << "]" << endl;
}
if(rep % 100 == 0) {
cout << rep << " Cases Completed!" << endl;
}
}
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int N, K, Q;
cin >> N >> K >> Q;
vector<int> X(N), T(N), A(N), B(N), L(Q), Y(Q);
for(int i = 0; i < N; ++i) {
cin >> X[i] >> T[i] >> A[i] >> B[i];
}
for(int i = 0; i < Q; ++i) {
cin >> L[i] >> Y[i];
}
vector<int> ans = solve_easy(N, K, Q, X, T, A, B, L, Y);
for(int i = 0; i < Q; ++i) {
cout << ans[i] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5063 ms |
15892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5045 ms |
15672 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
