| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 538578 | huangqr | Event Hopping 2 (JOI21_event2) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll,ll>;
using ppl = pair<pl,pl>;
const ll lim=5e5+5, b = 405;//b is the block size
ll nxt[lim], jumps[lim], out[lim];
set<pl>s;
ll journey(ll start){
auto it=s.lower_bound(make_pair(start,-1ll));
ll block = it->first;//block is the LAST position we CAN go
ll ans = 0;
ll pos = start;
while(pos<=l&&out[pos]<=block){
ans += jumps[pos] + 1;
pos = out[pos];
}
while(pos<=l&&nxt[pos]<=block){
ans ++;
pos = nxt[pos];
}
return ans;
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
ll n,k;
cin>>n>>k;
vector<ll>dsc;
unordered_map<ll,ll>d;
vector<pl>v;
for(int i=0;i<n;i++){
ll a,b;
cin>>a>>b;
v.emplace_back(a,b);
dsc.push_back(a);
dsc.push_back(b);
}
sort(dsc.begin(),dsc.end());
dsc.erase(unique(dsc.begin(),dsc.end()),dsc.end());
for(int i=0;i<(int)dsc.size();i++)d[dsc[i]]=i+1;
for(auto &p:v)p.first=d[p.first],p.second=d[p.second];
ll l = dsc.size();
fill(nxt,nxt+l+2,1e18);
for(auto p:v)nxt[p.first]=min(nxt[p.first],p.second);
for(int i=l;i>=1;i--)nxt[i]=min(nxt[i],nxt[i+1]);
for(int i=1;i<=l;i+=b){
int last = min(l,i+l-1);
for(int j=last;j>=i;j--){
if(nxt[j]>last){
jumps[j]=0;
out[j]=nxt[j];
}
else{
jumps[j]=jumps[nxt[j]]+1;
out[j]=out[nxt[j]];
}
}
}
s.emplace(0,1);
s.emplace(l,l+1);
ll cur = journey(1);
if(cur<k){
cout<<"-1\n";
return 0;
}
vector<ll>ans;
for(int i=0;i<n&&ans.size()<k;i++){
auto it=s.lower_bound(make_pair(v[i].first,-1ll));
if(it->first<v[i].second)continue;
it--;
if(it->second>v[i].first)continue;
ll org_start = it->second;
ll org_this_seg = journey(org_start);
s.insert(v[i]);
ll new_this_seg = journey(org_start) + journey(v[i].second);
assert(new_this_seg <= org_this_seg);
if(cur - org_this_seg + new_this_seg + s.size() >=k){
cur -= org_this_seg;
cur += new_this_seg;
ans.push_back(i+1);
}
else{
s.erase(v[i]);
}
}
for(auto x:ans)cout<<x<<"\n";
//for(int i=1;i<=l;i++)cout<<jumps[i]<<" ";
//for(auto x:v)cout<<x.first<<" "<<x.second<<"\n";
//cout<<"\n\n";
}