Ryhmät

input/code.cpp: In function 'int cnt_fst(std::bitset<100000>&, int)':
input/code.cpp:13:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::size_t' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   for (int i = 0; i < bs.size(); i) {
      |                   ~~^~~~~~~~~~~
input/code.cpp:13:34: warning: for increment expression has no effect [-Wunused-value]
   13 |   for (int i = 0; i < bs.size(); i) {
      |                                  ^
input/code.cpp:14:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::size_t' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     if (i + Y < bs.size()) {
      |         ~~~~~~^~~~~~~~~~~

#include <bits/stdc++.h>
#pragma GCC target("popcnt")

#define N 100000

using namespace std;

#define Y 512

int cnt_Y(const std::bitset<Y> &lol) { return lol.count(); }
int cnt_fst(bitset<100000> &bs, int n) {
  int cnt = 0;
  for (int i = 0; i < bs.size(); i) {
    if (i + Y < bs.size()) {
      int cnt2 = cnt_Y(*(((bitset<Y> *)(((char *)(&bs)) + (i / 8)))));
      if (cnt2 + cnt < n) {
        i += Y;
        cnt += cnt2;
        continue;
        // return i;
      }
    }
    if (bs[i])
      cnt++;
    if (cnt == n)
      return i;
    i++;
  }
  return -1;
}

void bsprint(bitset<100000> &bs) {
  for (int i = 10; i >= 0; i--) {
    cout << bs[i];
  }
  cout << endl;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, t;
  cin >> n >> t;
  vector<int> a(n), b(n);
  vector<pair<int, int>> childrenA;
  vector<pair<int, int>> childrenB;
  array<bitset<100000>, 100001> A, B;
  vector<pair<int, int>> QAQ;
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
    QAQ.push_back({b[i], a[i]});
  }
  sort(QAQ.begin(), QAQ.end());
  for (int i = 0; i < n; i++) {
    childrenA.push_back({QAQ[i].second, i});
    childrenB.push_back({QAQ[i].first, i});
  }
  sort(childrenA.begin(), childrenA.end());
  sort(childrenB.begin(), childrenB.end());
  vector<pair<int, pair<bitset<100000>, vector<pair<int, pair<int, bool>>>>>>
      ABH;
  bitset<100000> bs;
  ABH.push_back({0, {bs, {}}});
  auto it = childrenA.begin();
  auto it2 = childrenB.begin();
  vector<pair<int, pair<int, bool>>> mem;
  for (int i = 1; i <= n; i++) {
    while (it != childrenA.end() && it->first == i) {
      bs.set(it->second);
      mem.push_back({i, {it->second, true}});
      it++;
    }
    while (it2 != childrenB.end() && it2->first == i - 1) {
      bs.reset(it2->second);
      mem.push_back({i, {it2->second, false}});
      it2++;
    }
    if (mem.size() > 150) { // whatever factor
      (ABH[ABH.size() - 1]).second.second = mem;
      ABH.push_back({i, {bs, {}}});
      mem.clear();
    }
    if (i == n && mem.size() > 0) {
      ABH[ABH.size() - 1].second.second = mem;
      ABH.push_back({i, {bs, {}}});
      mem.clear();
    }
  }
  while (t--) {
    int m;
    cin >> m;
    bitset<100000> C;
    C.set();
    C >>= (100000 - n);
    vector<int> k(m);
    for (int i = 0; i < m; i++)
      cin >> k[i];
    sort(k.begin(), k.end());
    bool ok = true;
    for (int i = 0; i < m; i++) {
      int cr = k[i];
      auto rslt =
          upper_bound(ABH.begin(), ABH.end(), cr,
                      [](const auto &a, const auto &b) { return a < b.first; });
      rslt--;
      bitset<100000> AB = ((*(rslt))).second.first;
      for (auto &u : (*(rslt)).second.second) {
        if (u.first > cr)
          break;
        AB[u.second.first] = u.second.second;
      }
      auto candidates = AB & C;
      int until = cnt_fst(candidates, cr);
      if (until == -1) {
        ok = false;
        break;
      }
      candidates <<= (100000 - until - 1);
      candidates >>= (100000 - until - 1);
      C ^= candidates;
    }

    if (ok) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED