제출 #1197578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197578		mychecksedad	Event Hopping 2 (JOI21_event2)	C++20	1 / 100	111 ms	14096 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][2];
void build(int j){
  for(int i = 0; i <= 2*sz + 1; ++i) T[i][j] = 0;
}
void upd(int v, int val, int j){
  v += sz;
  T[v][j] = max(T[v][j], val);
  for(v >>= 1; v > 0; v >>= 1) T[v][j] = max(T[v<<1][j], T[v<<1|1][j]);
}
int get(int l, int r, int j){
  l += sz;
  r += sz + 1;
  int res = 0;
  for(; l < r; l >>= 1, r >>= 1){
    if(l&1) res = max(res, T[l++][j]);
    if(r&1) res = max(res, T[--r][j]);
  }
  return res;
}
void upd2(int l, int r, int val, int j){
  l += sz;
  r += sz + 1;
  for(; l < r; l >>= 1, r >>= 1){
    if(l&1) T[l++][j] += val;
    if(r&1) T[--r][j] += val;
  }
}
int get2(int v, int j){
  v += sz;
  int res = T[v][j];
  for(v >>= 1; v > 0; v >>= 1) res += T[v][j];
  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(0);
  vector<array<int, 2>> dp(m + 6);
  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, 0) + 1);
    upd(R, dp[R][0], 0);
  }
  for(int i = 1; i <= m; ++i) dp[i][0] = max(dp[i][0], dp[i - 1][0]);
  

  sort(a+1, a+1+n, [&](const array<int, 3> &x, const array<int, 3> &y){
    return x[1] < y[1];
  });

  build(1);

  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) + 1);
    upd(L, dp[L][1], 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;
  }

  build(0);
  build(1);
  // for(int i = 1; i <= m; ++i){
  //   cout << dp[i][0]  << ' ';
  // }
  // en;en;

  vi res;
  set<array<int, 5>> 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] - get2(R, 0);
    int rdp = dp[L][1] - get2(L, 1);

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

        if(dp[L][1] - dp[R][1] > 1){
          upd2(1, L, dp[L][1] - dp[R][1] - 1, 1);
        }
      }
    }
  }

  // for(auto [l, r, ldp, rdp, i]: S) cout << l << ' ' << r << ' ' << ldp << ' ' << rdp << ' ' << i << '\n';

  if(res.size() < k){
    cout << -1;
    en;
    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