Submission #66019

#TimeUsernameProblemLanguageResultExecution timeMemory
66019funcsrNew Home (APIO18_new_home)C++17
47 / 100
5061 ms361460 KiB
#pragma GCC optimize ("O3") #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <set> #include <cassert> 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 MOD 1000000007 #define MAX_N (1<<19) struct PQ { int size = 0; priority_queue<int> pq_max, erase_max; priority_queue<int, vector<int>, greater<int> > pq_min, erase_min; void add(int x) { size++; pq_min.push(x); pq_max.push(x); } void erase(int x) { size--; erase_min.push(x); erase_max.push(x); } bool empty() { return size==0; } int min() { while (!erase_min.empty() && pq_min.top() == erase_min.top()) pq_min.pop(), erase_min.pop(); return pq_min.top(); } int max() { while (!erase_max.empty() && pq_max.top() == erase_max.top()) pq_max.pop(), erase_max.pop(); return pq_max.top(); } }; inline int dist(PQ &s, int d) { if (s.empty()) return 0; //else return max(abs(d-*s.begin()), abs(d-*s.rbegin())); else return max(d-s.min(), s.max()-d); } struct SegTree { PQ 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].add(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) { seg[k].erase(x); 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 X[300000], 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]; int rangeL[300000], rangeR[300000]; int ans[300000]; vector<int> years, xs; inline void updateRangeL(int id, int l) { rangeL[id] = lower_bound(all(xs), l) - xs.begin(); } inline void updateRangeR(int id, int r) { rangeR[id] = upper_bound(all(xs), r) - xs.begin() - 1; } inline void addRange(int id) { int l = rangeL[id], r = rangeR[id]; if (rangeL[id] <= r) seg.add(l, r+1, X[id]); } inline void removeRange(int id) { int l = rangeL[id], r = rangeR[id]; if (l <= r) 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); int a = -1, b = -1; if (it != kind[k].end()) b = it->_2; if (it != kind[k].begin()) a = (--it)->_2; kind[k].insert(val); if (a != -1) removeRange(a); if (b != -1) removeRange(b); if (a == -1) updateRangeL(x, 0); else { updateRangeR(a, (X[a]+X[x])/2); updateRangeL(x, (X[a]+X[x])/2); } if (b == -1) updateRangeR(x, 2e8); else { updateRangeR(x, (X[b]+X[x])/2); updateRangeL(b, (X[b]+X[x])/2); } if (a != -1) addRange(a); if (b != -1) 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); int a = -1, b = -1; if (it != kind[k].end()) b = it->_2; if (it != kind[k].begin()) a = (--it)->_2; if (a != -1) removeRange(a); if (b != -1) removeRange(b); removeRange(x); if (a != -1) updateRangeR(a, (b==-1)?2e8:((X[a]+X[b])/2)); if (b != -1) updateRangeL(b, (a==-1)?0:((X[a]+X[b])/2)); if (a != -1) addRange(a); if (b != -1) addRange(b); } inline int maxDist(int pos) { return seg.query(index(xs, pos), pos); } signed main() { scanf("%d %d %d", &N, &K, &Q); rep(i, N) { scanf("%d %d %d %d", &X[i], &T[i], &A[i], &B[i]); X[i] *= 2; T[i]--; } rep(i, Q) { scanf("%d %d", &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); sort(all(xs)); uniq(xs); int zero = K; rep(y, years.size()) { for (int i : Gopen[y]) { if (kind[T[i]].empty()) zero--; add(T[i], P(X[i], i)); } for (int i : Gclose[y]) { remove(T[i], P(X[i], i)); if (kind[T[i]].empty()) zero++; } for (int q : Gquery[y]) { int m = -1; if (zero == 0) m = maxDist(L[q])/2; ans[q] = m; } } rep(i, Q) printf("%d\n", ans[i]); return 0; }

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:11: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:185:3: note: in expansion of macro 'rep'
   rep(y, years.size()) {
   ^~~
new_home.cpp:164:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &N, &K, &Q);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:166:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &X[i], &T[i], &A[i], &B[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:171:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &L[i], &Y[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...