Ryhmät

input/code.cpp: In function 'void solveTest(int)':
input/code.cpp:66:8: warning: unused variable 'groupTotal' [-Wunused-variable]
   66 |     ll groupTotal = groupSize * groupCnt;
      |        ^~~~~~~~~~

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) 0xffff
#endif

#define N 101010

int fen[N];
void add(int i, int v) {
  for (; i <= N; i+=i&-i) fen[i] += v;
}
int sumq(int i) {
  int sm = 0;
  for (; i >= 1; i-=i&-i) sm+=fen[i];
  return sm;
}

vector<pair<ll,ll>> groupSizeBlocks[N];
vector<ll> needSum[N];
vector<int> distSol[N]; // how many are between a and b for test t
ll reqSum[N];
vector<int> startsAt[N];

struct Query {
  int l, r, testId, idxOfGroup;
};

vector<Query> queries;

int countOfL[N], countOfR[N], prefL[N], prefR[N];
int n, t;

ll capableOfPoint(int groupSize) {
  return prefL[groupSize] - prefR[groupSize-1];
}

ll stillNotEnded(int groupSize) {
  return n - prefR[groupSize - 1];
}

void solveTest(int ti) {
  int df = groupSizeBlocks[ti].size();
  if (reqSum[ti] > n) return void(cout << "NO\n");
  if (df == 0) return void(cout << "YES\n");

  vector<ll> totalNeed(df+1, 0);

  for (int i = 0; i < df; i++) {
    auto bl = groupSizeBlocks[ti][i];
    ll groupSize = bl.first;
    ll groupCnt = bl.second;
    ll groupTotal = groupSize * groupCnt;
    if (groupTotal > capableOfPoint(groupSize)) return void(cout << "NO\n");
    totalNeed[i + 1] = totalNeed[i] + groupTotal;
    if (totalNeed[i + 1] > prefL[groupSize]) return void(cout << "NO\n");
  }
  for (int i = 0; i < df; i++) {
    auto bl = groupSizeBlocks[ti][i];
    ll groupSize = bl.first;
    ll groupCnt = bl.second;
    ll groupTotal = groupSize * groupCnt;
    ll afterThis = totalNeed[df] - totalNeed[i];
    if (afterThis > stillNotEnded(groupSize)) return void(cout << "NO\n");
  }

  vector<ll> pr;
  pr.push_back(0);
  for (int i = 1; i < df; i++) {
    // cout<<"currently adding: "<<pr[i-1]+distSol[ti][i-1]<<"\n";
    pr.push_back(pr[i - 1] + distSol[ti][i - 1]);
  }

  ll worst = 1000000000000000LL;
  for (int i = 1; i <= df; i++) {
    int prevSize = groupSizeBlocks[ti][i-1].first;
    ll b = totalNeed[i-1]-prefR[prevSize-1]+pr[i-1];
    if (b<worst) worst = b;
    ll a= totalNeed[i]-prefL[prevSize]+pr[i-1];
    if (a > worst) return void(cout << "NO\n");
  }

  cout << "YES\n";
}

void solve() {
  for (int ti = 0; ti < t; ti++) {
    int m; cin>>m;
    vector<int> groupSizeDemands(m);
    ll reqKids = 0;
    for (int j = 0; j < m; j++) {
      cin>>groupSizeDemands[j];
      reqKids += groupSizeDemands[j];
    }
    if (m == 0) {
      groupSizeBlocks[ti].clear();
      reqSum[ti] = 0;
      distSol[ti].clear();
      continue;
    }
    sort(groupSizeDemands.begin(), groupSizeDemands.end());

    pair<ll, ll> curBlock = {groupSizeDemands[0], 1}; // sum, cnt
    vector<pair<ll, ll>> blockSizes;

    for (int i = 1; i < m; i++) {
      ll demand = groupSizeDemands[i];
      if (demand != curBlock.first) {
        // add block
        blockSizes.push_back(curBlock);
        curBlock = {demand, 1};
        continue;
      }
      // same demand so stack this
      curBlock.second++;
    }
    if (curBlock.second != 0) blockSizes.push_back(curBlock);
    groupSizeBlocks[ti] = blockSizes;
    
    reqSum[ti] = reqKids;

    int df = blockSizes.size();
    distSol[ti].assign(max(df-1, 0), 0);

    // take adjacent differences between distinct group sizes (empty space)
    for (int i = 0; i < df-1; i++) {
      int l = blockSizes[i].first + 1;
      int r = blockSizes[i+1].first - 1;
      if (l <= r) queries.push_back({l, r, ti, i});
    }
  }

  sort(queries.begin(), queries.end(), [&](auto& a, auto& b) {
    return a.l > b.l;
  });

  int cur = n;
  for (auto& q: queries) {
    while (cur >= q.l) {
      for (int endPoint : startsAt[cur]) {
        add(endPoint, 1);
        // cout << "adding to "<<endPoint<<"\n";
      }
      cur--;
    }
    distSol[q.testId][q.idxOfGroup] = sumq(q.r);
  }
  
  for (int ti = 0; ti < t; ti++) {
    solveTest(ti);
  }
}



int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  cin>>n>>t;

  for (int i = 0; i < n; i++) {
    int a, b; cin>>a>>b;
    countOfL[a]++;
    countOfR[b]++;
    startsAt[a].push_back(b);
  }

  for (int i = 1; i <= n; i++) {
    prefL[i] = prefL[i-1] + countOfL[i];
    prefR[i] = prefR[i-1] + countOfR[i];
  }

  solve();
}

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: ACCEPTED

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