Submission #1127683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127683		VinhLuu	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	25 ms	4028 KiB

event2

#include <bits/stdc++.h>
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;

#define lpv

#ifndef lpv
#include "AC.h"
#endif // lpv

#define int long long

const int N = 2e5 + 5;

int n, k, a[N], b[N];

int st[N << 2], lz[N << 2], m;

vector<int> rrh;

void build(int i,int l,int r) {
  if(l == r) {
    st[i] = lz[i] = 0;
    return;
  }
  int mid = (l + r) / 2;
  build(i << 1, l, mid);
  build(i << 1|1, mid + 1, r);
  st[i] = lz[i] = 0;
}

void dolz(int i) {
  if(!lz[i]) return;
  int x = lz[i]; lz[i] = 0;
  lz[i << 1] += x;
  lz[i << 1|1] += x;
  st[i << 1] += x;
  st[i << 1|1] += x;
}

void update(int i,int l,int r,int u,int v) {
  if(l > r || r < u || v < l) return;
  if(u <= l && r <= v) {
    st[i] += 1;
    lz[i] += 1;
    return;
  }
  dolz(i);
  int mid = (l + r) / 2;
  update(i << 1, l, mid, u, v);
  update(i << 1|1, mid + 1, r, u, v);
  st[i] = st[i << 1] + st[i << 1|1];
}

int get(int i,int l,int r,int u,int v) {
  if(l > r || r < u || v < l || u > v) return 0;
  if(u <= l && r <= v) return st[i];
  dolz(i);
  int mid = (l + r) / 2;
  return get(i << 1, l, mid, u, v) + get(i << 1|1, mid + 1, r, u, v);
}

namespace sub1 {

  bool cmp(vector<int> &x, vector<int> &y) {
    return x.empty();
    for(int i = 0; i < k; i ++) if(x[i] != y[i]) return x[i] < y[i];
    return 0;
  }

  void solve() {
    vector<int> kq;
    for(int msk = 0; msk < (1 << n); msk ++) {
      int u = __builtin_popcount(msk);
      if(u != k) continue;
      bool ff = true;
      vector<int> vr;
      map<int,bool> mp;
      build(1, 1, n);
      for(int i = 1; i <= n; i ++) if(msk >> (i - 1) & 1) {
        vr.push_back(i);
        if(a[i] + 1 == b[i]) {
          if(mp[b[i]]) {
            ff = false;
            break;
          }
          mp[b[i]] = 1;
          continue;
        }
        int _left = lower_bound(all(rrh), a[i]) - rrh.begin() + 1;
        int _right = upper_bound(all(rrh), b[i]) - rrh.begin();
        if(get(1, 1, m, _left, _right)) {
          ff = false;
          break;
        }
        _left = lower_bound(all(rrh), a[i] + 1) - rrh.begin() + 1;
        _right = lower_bound(all(rrh), b[i] - 1) - rrh.begin() + 1;
        update(1, 1, m, _left, _right);
      }
      if(!ff) continue;
      if(cmp(kq, vr)) kq = vr;
    }
    if(kq.empty()) cout << -1;
    else for(auto i : kq) cout << i << "\n";
  }
}

#ifdef lpv
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")) {
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n >> k;
  for(int i = 1; i <= n; i ++) {
    cin >> a[i] >> b[i];
  }
  for(int i = 1; i <= n; i ++) if(a[i] < b[i] - 1) {
    rrh.push_back(a[i] + 1);
    rrh.push_back(b[i] - 1);
  }
  sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());

  m = (int)rrh.size();

  sub1 :: solve();

}
#endif // lpv

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:115:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
event2.cpp:116:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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