# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
894557 | 2023-12-28T12:48:15 Z | ReLice | Event Hopping 2 (JOI21_event2) | C++14 | 219 ms | 72752 KB |
#include <bits/stdc++.h> #define ll long long #define str string #define ins insert #define ld long double #define pb push_back #define pf push_front #define pof pop_front() #define pob pop_back() #define lb lower_bound #define ub upper_bound #define endl "\n" #define fr first #define sc second #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define sz size() #define vll vector<ll> #define bc back() #define arr array using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template <class _T> bool chmin(_T &x, const _T &y){ if (x>y)x=y; return x>y; } template <class _T> bool chmax(_T &x, const _T &y){ if (x<y)x=y; return x<y; } #define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);} void start(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } const ll inf=1e18+7; const ll mod=1e9+7; const ll N=3e5+5; const ld eps=1e-9; ll p[N][21]; ll dp(ll l,ll r){ ll sum=0; for(ll i=20;i>=0;i--){ if(p[l][i]<=r){ sum+=(1ll<<i); l=p[l][i]; } } return sum; } void solve(){ ll i,j; ll n,k; ll a,b; cin>>n>>k; ll l[n],r[n]; set<ll> st; for(i=0;i<n;i++){ cin>>l[i]>>r[i]; st.ins(l[i]); st.ins(r[i]); } //compress map<ll,ll> comp; ll c=0; for(auto i : st){ comp[i]=++c; } for(i=0;i<n;i++){ l[i]=comp[l[i]]; r[i]=comp[r[i]]; } //building graph ll m=n*2; ll suf[m+5]; for(i=0;i<m+2;i++) suf[i]=m+1; vector<vll> v(m+5); for(i=0;i<n;i++){ v[l[i]].pb(r[i]); } for(i=m;i>0;i--){ suf[i]=suf[i+1]; for(auto j : v[i])chmin(suf[i],j); } for(i=1;i<=m;i++){ p[i][0]=suf[i]; } for(i=m;i>0;i--){ for(j=1;j<=20;j++){ p[i][j]=p[p[i][j-1]][j-1]; } } //answer set<pair<ll,ll>> rng; rng.ins({1,m}); ll al=dp(1,m); if(dp(1,m)<k){ cout<<-1<<endl; return; } for(i=0;i<n;i++){ auto it=rng.ub({l[i],inf}); it--; ll L=it->fr,R=it->sc; if(R<r[i])continue; if(al-dp(L,R)+dp(L,l[i])+dp(r[i],R)+1>=k){ al=al-dp(L,R)+dp(L,l[i])+dp(r[i],R)+1; k--; cout<<i+1<<endl; if(k==0)return; rng.erase(it); rng.ins({L,l[i]}); rng.ins({r[i],R}); } } } signed main(){ start(); ll t=1; //cin>>t; while(t--) solve(); return 0; } /* 4 2 1 4 3 5 4 9 7 10 */
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 600 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Incorrect | 219 ms | 72752 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 600 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Incorrect | 219 ms | 72752 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |