제출 #265245

#제출 시각아이디문제언어결과실행 시간메모리
265245extraterrestrial새 집 (APIO18_new_home)C++14
0 / 100
1033 ms178920 KiB
#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]; set<int> flex[N]; int ans[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]].insert(x[i]); } for (int i = 0; i < q; i++) { pos[i] = upper_bound(all(coord), pos[i]) - coord.begin(); } 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].begin(), *flex[cur_type].begin()); //update_min(1, 1, SZ(coord), *(--flex[cur_type].end()), SZ(coord), *(--flex[cur_type].end())); auto it = flex[cur_type].begin(); for (;;) { auto it2 = it; it2++; if (it2 == flex[cur_type].end()) { break; } int l = *it, r = *it2; while (r - l > 1) { int mid = (l + r) / 2; if (coord[mid - 1] - coord[*it - 1] <= coord[*it2 - 1] - coord[mid - 1]) { l = mid; } else { r = mid; } } //update_min(1, 1, SZ(coord), *it, l, *it); //update_max(1, 1, SZ(coord), r, *it2, *it2); it++; } } 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]) { if (have_empty) { ans[it.S] = 1e9; continue; } if (it.F < 1 || it.F > SZ(coord)) { exit(0); } int lpos = get_min(1, 1, SZ(coord), it.F), rpos = get_max(1, 1, SZ(coord), it.F); if (lpos <= it.F) { if (lpos < 1 || lpos > SZ(coord)) { exit(0); } ans[it.S] = max(ans[it.S], coord[it.F - 1] - coord[lpos - 1]); } if (rpos >= it.F) { if (rpos < 1 || rpos > SZ(coord)) { exit(0); } ans[it.S] = max(ans[it.S], coord[rpos - 1] - coord[it.F - 1]); } } /*for (auto cpar : del[cur_time]) { if (have_empty) { break; } flex[cpar.S].erase(flex[cpar.S].find(cpar.F)); if (flex[cpar.S].find(cpar.F) != flex[cpar.S].end()) { continue; } if (flex[cpar.S].empty()) { have_empty = true; break; } auto it2 = flex[cpar.S].upper_bound(cpar.F); if (it2 == flex[cpar.S].end()) { update_min(1, 1, SZ(coord), *flex[cpar.S].rbegin(), SZ(coord), *flex[cpar.S].rbegin()); } else if (it2 == flex[cpar.S].begin()) { update_max(1, 1, SZ(coord), 1, *flex[cpar.S].begin(), *flex[cpar.S].begin()); } else { auto it = it2; it--; if (*it >= cpar.F || *it2 <= cpar.F) { exit(0); } int l = *it, r = *it2; while (r - l > 1) { int mid = (l + r) / 2; if (coord[mid - 1] - coord[*it - 1] <= coord[*it2 - 1] - coord[mid - 1]) { l = mid; } else { r = mid; } } update_min(1, 1, SZ(coord), *it, l, *it); update_max(1, 1, SZ(coord), l + 1, *it2, *it2); } }*/ } for (int i = 0; i < q; i++) { if (ans[i] == 1e9) { cout << -1 << '\n'; } else { cout << ans[i] << '\n'; } } }
#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...