제출 #1034026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1034026		NeroZein	Event Hopping 2 (JOI21_event2)	C++17	8 / 100	106 ms	14644 KiB

event2

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 1e5 + 5;

struct segtree {
  vector<int> seg;
  segtree() {
    seg.resize(N * 4); 
  }
  void upd(int nd, int l, int r, int p, int v, bool f = false) {
    if (l == r) {
      seg[nd] = (f ? v : max(seg[nd], v));
      return;
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (p <= mid) {
      upd(nd + 1, l, mid, p, v, f); 
    } else {
      upd(rs, mid + 1, r, p, v, f); 
    }
    seg[nd] = max(seg[nd + 1], seg[rs]); 
  }

  int qry(int nd, int l, int r, int s, int e) {
    if (l >= s && r <= e) {
      return seg[nd]; 
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (mid >= e) {
      return qry(nd + 1, l, mid, s, e);
    } else {
      if (mid < s) {
        return qry(rs, mid + 1, r, s, e);
      } else {
        return max(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e));
      }
    }
  }
  
  int dive(int nd, int l, int r, int v) {
    if (l == r) {
      return l;
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (seg[nd + 1] >= v) {
      return dive(nd + 1, l, mid, v); 
    }
    return dive(rs, mid + 1, r, v); 
  }
};

int compress(vector<array<int, 3>>& a) {
  int n = (int) a.size();
  vector<int> vec; 
  for (int i = 0; i < n; ++i) {
    vec.push_back(a[i][0]);
    vec.push_back(a[i][1]);
  }
  sort(vec.begin(), vec.end());
  vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
  for (int i = 0; i < n; ++i) {
    a[i][0] = lower_bound(vec.begin(), vec.end(), a[i][0]) - vec.begin();
    a[i][1] = lower_bound(vec.begin(), vec.end(), a[i][1]) - vec.begin();
  }
  return (int) vec.size();
}

bool fit(int l, int r, set<pair<int, int>>& se) {
  auto it = se.upper_bound({l, INT_MAX});
  if (it != se.end() && it->first < r) {
    return false; 
  }
  if (it != se.begin() && prev(it)->second > l) {
    return false;
  }
  return true;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  vector<array<int, 3>> a(n); 
  for (int i = 0; i < n; ++i) {
    cin >> a[i][0] >> a[i][1]; 
    a[i][2] = i;
  }
  int cnt = compress(a);
  sort(a.begin(), a.end(), [&](array<int, 3>& i, array<int, 3>& j) {
    return i[0] < j[0];
  });
  segtree dp;
  vector<int> start_at(n);
  for (int i = n - 1; i >= 0; --i) {
    auto [l, r, ind] = a[i];
    start_at[ind] = 1 + dp.qry(0, 0, cnt - 1, r, cnt - 1);
    dp.upd(0, 0, cnt - 1, l, start_at[ind]); 
  }
  fill(dp.seg.begin(), dp.seg.end(), 0);
  vector<int> end_at(n);
  for (int i = 0; i < n; ++i) {
    auto [l, r, ind] = a[i];
    end_at[ind] = 1 + dp.qry(0, 0, cnt - 1, 0, l);
    dp.upd(0, 0, cnt - 1, r, end_at[ind]);
  }
  sort(a.begin(), a.end(), [&](array<int, 3>& i, array<int, 3>& j) {
    return i[2] < j[2];
  });
  int ind = -1;
  for (int i = 0; i < n; ++i) {
    if (start_at[i] + end_at[i] - 1 >= k) {
      ind = i; 
      break; 
    }
  }
  if (ind == -1) {
    cout << -1 << '\n';
    return 0; 
  }
  vector<int> to_left, to_right;
  for (int i = 0; i < n; ++i) {
    if (i == ind) {
      continue;
    }
    if (a[i][1] <= a[ind][0]) {
      to_left.push_back(i);
    } else if (a[ind][1] <= a[i][0]) {
      to_right.push_back(i); 
    }
  }
  set<pair<int, int>> se;
  se.insert({a[ind][0], a[ind][1]});
  segtree left, right; //is it's range not occupied yet?
  fill(left.seg.begin(), left.seg.end(), -n);
  fill(right.seg.begin(), right.seg.end(), -n);
  for (int i : to_left) {
    left.upd(0, 0, n - 1, i, end_at[i]);
  }
  for (int i : to_right) {
    right.upd(0, 0, n - 1, i, start_at[i]); 
  }
  int rem = k - 1;
  vector<int> ans = {ind};
  int cur_pref = end_at[ind] - 1;
  int cur_suf = start_at[ind] - 1;
  while (rem) {
    int need_left = max(1, rem - cur_suf);
    int need_right = max(1, rem - cur_pref);
    int left_candidate = (left.seg[0] < need_left ? n : left.dive(0, 0, n - 1, need_left));
    int right_candidate = (right.seg[0] < need_right ? n : right.dive(0, 0, n - 1, need_right));
    if (left_candidate < right_candidate) {
      if (fit(a[left_candidate][0], a[left_candidate][1], se)) {
        rem--;
        ans.push_back(left_candidate);
        cur_pref = end_at[left_candidate] - 1; 
        se.insert({a[left_candidate][0], a[left_candidate][1]});
      }
      left.upd(0, 0, n - 1, left_candidate, -n, 1); 
    } else {
      if (fit(a[right_candidate][0], a[right_candidate][1], se)) {
        rem--;        
        ans.push_back(right_candidate); 
        cur_suf = start_at[right_candidate] - 1; 
        se.insert({a[right_candidate][0], a[right_candidate][1]});
      }
      right.upd(0, 0, n - 1, right_candidate, -n, 1); 
    }
    //debug(se); 
  }
  assert(rem == 0);
  sort(ans.begin(), ans.end());
  for (int i = 0; i < k; ++i) {
    cout << ans[i] + 1 << '\n';
  }
  return 0;
}

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