Submission #1008666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008666		AdamGS	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	185 ms	34252 KiB

event2

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7, LG=20;
pair<int,int>T[LIM];
int nxt[2*LIM][LG], akt, sum, n, k;
vector<int>skal;
map<int,int>mp;
set<pair<int,int>>S;
int licz(int a, int b) {
  if(a>b) return 0;
  int p=0;
  for(int i=LG-1; i>=0; --i) if(nxt[a][i]<=b) {
    p+=1<<i;
    a=nxt[a][i];
  }
  return p;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> k;
  rep(i, n) {
    cin >> T[i].st >> T[i].nd;
    skal.pb(T[i].st);
    skal.pb(T[i].nd);
  }
  sort(all(skal));
  for(auto i : skal) if(mp.find(i)==mp.end()) mp[i]=akt++;
  rep(i, n) T[i]={mp[T[i].st], mp[T[i].nd]};
  rep(i, akt+1) nxt[i][0]=akt;
  rep(i, n) nxt[T[i].st][0]=min(nxt[T[i].st][0], T[i].nd);
  for(int i=akt-1; i>=0; --i) nxt[i][0]=min(nxt[i][0], nxt[i+1][0]);
  for(int j=1; j<LG; ++j) {
    rep(i, akt+1) nxt[i][j]=nxt[nxt[i][j-1]][j-1];
  }
  S.insert({0, akt-1});
  sum=licz(0, akt-1);
  if(sum<k) {
    cout << -1 << '\n';
    return 0;
  }
  vector<int>ans;
  rep(i, n) {
    auto it=S.lower_bound({T[i].st+1, -1});
    if(it==S.begin()) continue;
    --it;
    auto a=*it;
    if(a.st>T[i].st || T[i].nd>a.nd) continue;
    int p=sum-licz(a.st, a.nd)+licz(a.st, T[i].st)+licz(T[i].nd, a.nd)+1;
    if(p>=k) {
      sum=p;
      S.erase(a);
      if(a.st<T[i].st) S.insert({a.st, T[i].st});
      if(T[i].nd<a.nd) S.insert({T[i].nd, a.nd});
      ans.pb(i);
      if(ans.size()==k) break;
    }
  }
  for(auto i : ans) cout << i+1 << '\n';
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:62:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |       if(ans.size()==k) break;
      |          ~~~~~~~~~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61