제출 #398084

#제출 시각아이디문제언어결과실행 시간메모리
39808412tqianEvent Hopping 2 (JOI21_event2)C++17
0 / 100
368 ms32960 KiB
#include <bits/stdc++.h> using namespace std; #define f1r(i, a, b) for (int i = a; i < b; ++i) #define f0r(i, a) f1r(i, 0, a) #define each(t, a) for (auto& t : a) #define mp make_pair #define f first #define s second #define pb push_back #define eb emplace_back #define sz(x) (int)(x).size() #define all(x) begin(x), end(x) typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<pi> vpi; typedef vector<pl> vpl; template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } template <class T> int get_pos(vector<T>& v, T x) { return lower_bound(all(v), x) - v.begin(); } const int INF = 1e9; const int INF2 = 5e8; struct SegmentTree { vpi st; int sz; int ty = 0; int nil; void init(int n, int t) { ty = t; if (ty == 0) { nil = INF; } else { nil = -INF; } sz = 1; while (sz < n) sz <<= 1; st.assign(2 * sz, mp(nil, 0)); f0r(i, sz) st[i + sz].s = i; } pi comb(pi x, pi y) { if (ty == 0) return min(x, y); return max(x, y); } void pull(int i) { st[i] = comb(st[2 * i], st[2 * i + 1]); } void upd(int p, int x, int i = 1, int l = 0, int r = -1) { if (r == -1) r += sz; if (p < l || r < p) return; if (l == r) { st[i] = comb(st[i], {x, p}); return; } int m = (l + r) >> 1; upd(p, x, 2 * i, l, m); upd(p, x, 2 * i + 1, m + 1, r); pull(i); } pi query(int lo, int hi, int i = 1, int l = 0, int r = -1) { if (r == -1) r += sz; if (hi < l || r < lo) return {nil, nil}; else if (lo <= l && r <= hi) return st[i]; int m = (l + r) >> 1; return comb(query(lo, hi, 2 * i, l, m), query(lo, hi, 2 * i + 1, m + 1, r)); } }; struct IntervalUnion { set<pi> ivals; void insert(pi x) { ivals.insert(x); } bool bad(pi x) { auto it = ivals.lower_bound({x.f, -INF}); if (it != ivals.end()) { if (it->f == x.f) return true; if (it->f < x.s) return true; } if (it == ivals.begin()) return false; it = prev(it); if (it->s > x.f) return true; return false; } }; int main() { cin.tie(0)->sync_with_stdio(0); int n, k; cin >> n >> k; vpi v(n); f0r(i, n) cin >> v[i].f >> v[i].s; vi pts; each(p, v) pts.pb(p.f), pts.pb(p.s); sort(all(pts)); pts.erase(unique(all(pts)), pts.end()); each(p, v) p.f = get_pos(pts, p.f), p.s = get_pos(pts, p.s); map<pi, int> conv; // this is not unique possibly, but that doesn't matter f0r(i, n) conv[v[i]] = i; vi ord(n); iota(all(ord), 0); sort(all(ord), [&](int x, int y) { return v[x].f < v[y].f; }); int d = 1; while ((1 << d) < n) ++d; vector<vi> L, R; vector<vector<bool>> LB, RB; L = R = vector<vi>(d, vi(n)); LB = RB = vector<vector<bool>>(d, vector<bool>(n)); int sz = sz(pts); SegmentTree seg; seg.init(sz, 0); for (int i = n - 1; i >= 0; i--) { int id = ord[i]; int l = v[id].f; int r = v[id].s; auto res = seg.query(r, sz - 1); if (res.f != seg.nil) { R[0][id] = conv[{res.s, res.f}]; RB[0][id] = true; } else { R[0][id] = id; } seg.upd(l, r); } sort(all(ord), [&](int x, int y) { return v[x].s < v[y].s; }); seg.init(sz, 1); f0r(i, n) { int id = ord[i]; int l = v[id].f; int r = v[id].s; auto res = seg.query(0, l); if (res.f != seg.nil) { L[0][id] = conv[{res.f, res.s}]; LB[0][id] = true; } else { L[0][id] = id; } seg.upd(r, l); } f1r(j, 1, d) { f0r(i, n) { L[j][i] = L[j - 1][L[j - 1][i]]; R[j][i] = R[j - 1][R[j - 1][i]]; LB[j][i] = LB[j - 1][L[j - 1][i]] & LB[j - 1][i]; RB[j][i] = RB[j - 1][R[j - 1][i]] & RB[j - 1][i]; } } vi ans; IntervalUnion IU; auto overlap = [&](pi x, pi y) -> bool { if (x > y) swap(x, y); if (x.s <= y.f) return false; return true; }; auto compute = [&](int x, int y) -> int { // assumes nonoverlapping int amt = 0; if (x == -1 && y == -1) { amt = 0; } else if (x == -1) { // that means null left int cur = y; for (int i = d - 1; i >= 0; i--) { if (LB[i][cur]) continue; cur = L[i][cur]; amt += (1 << i); } } else if (y == -1) { int cur = x; for (int i = d - 1; i >= 0; i--) { if (RB[i][cur]) continue; cur = R[i][cur]; amt += (1 << i); } } else { if (v[x] > v[y]) swap(x, y); int cur = x; for (int i = d - 1; i >= 0; i--) { if (!RB[i][cur]) continue; auto g = R[i][cur]; if (v[g].s <= v[y].f) { amt += (1 << i); cur = g; } } } return amt; }; int cur = 0; f0r(i, n) { auto& p = v[i]; int l = p.f; int r = p.s; if (IU.bad(p)) continue; auto it = IU.ivals.upper_bound(p); int aft = -1; if (it != IU.ivals.end()) aft = conv[*it]; int bef = -1; if (it != IU.ivals.begin()) bef = conv[*prev(it)]; int now = compute(bef, aft); int future = compute(bef, i) + compute(i, aft); if (cur - now + future + 1 >= k) { cur = cur - now + future + 1; IU.insert(p); ans.pb(i); } } if (sz(ans) >= k) { f0r(i, k) cout << ans[i] + 1 << '\n'; } else { cout << -1 << '\n'; } return 0; } /** * store at left coordinate right coordinate, find minimum right coordinate */

컴파일 시 표준 에러 (stderr) 메시지

event2.cpp: In function 'int main()':
event2.cpp:231:13: warning: unused variable 'l' [-Wunused-variable]
  231 |         int l = p.f;
      |             ^
event2.cpp:232:13: warning: unused variable 'r' [-Wunused-variable]
  232 |         int r = p.s;
      |             ^
event2.cpp:188:10: warning: variable 'overlap' set but not used [-Wunused-but-set-variable]
  188 |     auto overlap = [&](pi x, pi y) -> bool {
      |          ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...