Submission #1197547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197547		mychecksedad	Event Hopping 2 (JOI21_event2)	C++20	1 / 100	109 ms	12608 KiB

event2

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


int sz, T[N];
void build(){
  for(int i = 0; i <= 2*sz + 1; ++i) T[i] = 0;
}
void upd(int v, int val){
  v += sz;
  T[v] = max(T[v], val);
  for(v >>= 1; v > 0; v >>= 1) T[v] = max(T[v<<1], T[v<<1|1]);
}
int get(int l, int r){
  l += sz;
  r += sz + 1;
  int res = 0;
  for(; l < r; l >>= 1, r >>= 1){
    if(l&1) res = max(res, T[l++]);
    if(r&1) res = max(res, T[--r]);
  }
  return res;
}


int n, k;
array<int, 3> a[N];
void solve(){
  cin >> n >> k;
  vi val;
  for(int i = 1; i <= n; ++i){
    cin >> a[i][0] >> a[i][1];
    a[i][2] = i;
    val.pb(a[i][0]);
    val.pb(a[i][1]);
  }
  val.pb(0);
  sort(all(val));
  val.erase(unique(all(val)), val.end());

  int m = val.size();
  --m;
  sort(a+1, a+1+n);
  sz = m;
  

  build();
  vector<array<int, 2>> dp(m + 1);
  for(int i = 1; i <= n; ++i){
    int L = lower_bound(all(val), a[i][0]) - val.begin();
    int R = lower_bound(all(val), a[i][1]) - val.begin();
    dp[R][0] = max(dp[R][0], get(1, L) + 1);
    upd(R, dp[R][0]);
  }
  for(int i = 1; i <= m; ++i) dp[i][0] = max(dp[i][0], dp[i - 1][0]);
  

  build();

  for(int i = n; i >= 1; --i){
    int L = lower_bound(all(val), a[i][0]) - val.begin();
    int R = lower_bound(all(val), a[i][1]) - val.begin();
    dp[L][1] = max(dp[L][1], get(R, m) + 1);
    upd(L, dp[L][1]);
  }
  for(int i = m - 1; i >= 1; --i) dp[i][1] = max(dp[i][1], dp[i + 1][1]);
    
  vi pos(n + 1);
  for(int i = 1; i <= n; ++i){
    pos[a[i][2]] = i;
  }

  vi res;
  set<array<int, 4>> S;
  for(int i = 1; i <= n; ++i){
    if(S.size() == k) break;
    int L = lower_bound(all(val), a[pos[i]][0]) - val.begin();
    int R = lower_bound(all(val), a[pos[i]][1]) - val.begin();
    int ldp = dp[R][0];
    int rdp = dp[L][1];

    if(ldp + rdp >= k + 1){
      auto it = S.upper_bound(array<int, 4>{R, -1, -1, -1});
      if(it != S.begin() && (*prev(it))[1] > L){
        continue;
      }
      int total_dp = 0, r_pos = m, l_pos = 1;
      if(it != S.end()) total_dp += (*it)[3], r_pos = (*it)[0];
      if(it != S.begin()) total_dp += (*prev(it))[2], l_pos = (*prev(it))[1];
      total_dp++;
      total_dp += dp[L][0] - dp[l_pos][0];
      total_dp += dp[R][1] - dp[r_pos][1];
      assert(R <= r_pos);
      assert(l_pos <= L);
      if(total_dp >= k){
        S.insert({L, R, ldp, rdp});
        res.pb(i);
      }
    }
  }

  if(res.size() < k){
    cout << -1;
    return;
  }

  sort(all(res));
  for(int x: res) cout << x << '\n';
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

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