Submission #978199

#	Time	Username	Problem	Language	Result	Execution time	Memory
978199		asdfgrace	Advertisement 2 (JOI23_ho_t2)	C++17	69 / 100	2094 ms	14076 KiB

Main

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

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

/*
for any given pair it's ez to check
if you can create an edge between them
probably can calc contrib
this way you can quickly check like how many people you can donate this book to?
note that you can only donate to someone else if your e-value is greater than theirs
at the very least
2^n sub is ez
what about n^2 then
you get a dag with each edge existing if i can infl j
ans = # of nodes with indeg 0

*/

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  vector<array<int, 2>> xe(n);
  int mne = 1e9 + 1, mxe = -1;
  for (int i = 0; i < n; i++) {
    cin >> xe[i][0] >> xe[i][1];
    mne = min(mne, xe[i][1]);
    mxe = max(mxe, xe[i][1]);
  }
  sort(xe.begin(), xe.end());
  auto it = unique(xe.begin(), xe.end());
  xe.erase(it, xe.end());
  n = (int) xe.size();
  if (mne == mxe) {
    cout << n << '\n';
    return 0;
  }
  vector<int> indeg(n, 0);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (j == i) continue;
      if (abs(xe[i][0] - xe[j][0]) <= xe[i][1] - xe[j][1]) {
        indeg[j]++;
      }
    }
  }
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    if (!indeg[i]) cnt++;
  }
  cout << cnt << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 0 / 31