제출 #443576

#제출 시각아이디문제언어결과실행 시간메모리
443576dutchEvent Hopping 2 (JOI21_event2)C++17
0 / 100
187 ms27040 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e16, LIM = 1e5+1, LOG = 18; template<class T> struct SegmentTree{ int n = 1, i; vector<T> a; T ID; function<T(T, T)> comb = [](T x, T y){ return min(x, y); }; SegmentTree(int N, T id) : ID(id) { while((n+=n)<N); a.assign(2*n, ID); } SegmentTree& operator[](int j){ i=j+n; return *this; } void operator=(T v){ for(a[i]=v; i/=2; ) a[i] = comb(a[2*i], a[2*i+1]); } T operator()(int l, int r){ T x = ID; for(l+=n, r+=n+1; l<r; l/=2, r/=2){ if(l & 1) x = comb(x, a[l++]); if(r & 1) x = comb(x, a[--r]); } return x; } int find(int x, int l, int r){ if(r <= i || a[x] < a[0]) return n; if(r - l < 2) return l; int m = (l + r) / 2, y = find(2*x, l, m); return y < n ? y : find(2*x+1, m, r); } int find(int l, T v){ // first value >= v with index >= l i = l; a[0] = v; return find(1, 0, n); } }; int n, k, l[LIM], r[LIM], byR[LIM], p[LIM], g[LOG][LIM], rS[LIM]; bool removed[LIM]; set<array<int, 2>> s, selected; const array<int, 2> ID = {INF, INF}; int best(int u, int v){ int res = 0; for(int i=LOG; --i>=0; ) if(g[i][u] < v) res |= (1<<i), u = g[i][u]; return res + 1; } signed main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> k; SegmentTree<int> maxL(n, -INF); SegmentTree<array<int, 2>> minL(n, ID); maxL.comb = [](int x, int y){ return max(x, y); }; for(int i=0; i<n; ++i) cin >> l[i] >> r[i]; iota(byR, byR+n, 0LL); sort(byR, byR+n, [](int &x, int &y){ return r[x] < r[y]; }); for(int i=0; i<n; ++i){ maxL[i] = l[byR[i]]; minL[i] = {l[byR[i]], byR[i]}; p[byR[i]] = i; rS[i] = r[byR[i]]; } g[0][n] = n; for(int j=0; j<LOG; ++j) for(int i=0; i<=n; ++i) g[j][i] = j ? g[j-1][g[j-1][i]] : min(n, maxL.find(i+1, r[byR[i]])); int curr = best(0, n); if(curr < k){ cout << -1; return 0; } s.insert({0, n}); auto remove = [&](int i){ if(!removed[i]){ removed[i] = 1; auto f = --s.lower_bound({p[i]+1, 0}); int a = (*f)[0], b = (*f)[1]; curr += (best(a, p[i]) + best(p[i]+1, b) - best(a, b)); s.erase(f); if(p[i]+1<b) s.insert({p[i]+1, b}); if(a < p[i]) s.insert({a, p[i]}); } }; for(int i=0, z=k; i<n && z; ++i){ if(removed[i]) continue; auto f = --s.lower_bound({p[i], 0}); int a = (*f)[0], b = (*f)[1]; int v = (best(a, p[i]) + best(p[i]+1, b) - best(a, b)); if(1 + v + curr < z) continue; --z; int y = lower_bound(rS, rS+n, l[i]+1) - rS; array<int, 2> j; while((j = minL(y, p[i])) != ID){ remove(j[1]); minL[p[j[1]]] = ID; } while((j = minL(p[i], n-1))[0] < r[i]){ remove(j[1]); minL[p[j[1]]] = ID; } cout << i+1 << '\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...