Submission #969648

#	Time	Username	Problem	Language	Result	Execution time	Memory
969648		duckindog	Teams (IOI15_teams)	C++17	34 / 100	4108 ms	19028 KiB

teams

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

const int N = 500'000 + 10;
int n;
int a[N], b[N];

void init(int n_, int a_[], int b_[]) { 
  n = n_;
  vector<pair<int, int>> p;
  for (int i = 0; i < n; ++i) p.push_back({a_[i], b_[i]});
  sort(p.begin(), p.end());
  for (int i = 0; i < n; ++i) tie(a[i], b[i]) = p[i];
}
int can(int m, int k[]) { 
  sort(k, k + m);
  priority_queue<int, vector<int>, greater<>> q;
  int it = 0;
  for (int i = 0; i < m; ++i) { 
    while (it < n && a[it] <= k[i]) q.push(b[it++]);
    int cnt = k[i];
    while (q.size() && cnt) { 
      cnt -= (q.top() >= k[i]);
      q.pop();
    }
    if (cnt) return 0;
  } 
  return 1;
}

#ifdef LOCAL
int n_, a_[N], b_[N];
int inQ;
int inM, inK[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n_;
  for (int i = 0; i < n_; ++i) cin >> a_[i] >> b_[i];
  init(n_, a_, b_);
  cin >> inQ;
  while (inQ--) { 
    cin >> inM;
    for (int i = 0; i < inM; ++i) cin >> inK[i];
    cout << can(inM, inK) << "\n";
  }
}
#endif

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23