Submission #111845

#TimeUsernameProblemLanguageResultExecution timeMemory
111845square1001New Home (APIO18_new_home)C++14
0 / 100
5063 ms15892 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...