Submission #899327

#	Time	Username	Problem	Language	Result	Execution time	Memory
899327		stefanneagu	Advertisement 2 (JOI23_ho_t2)	C++17	69 / 100	2067 ms	49904 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int nmax = 5e5 + 1;
 
struct str {
  int a, b;
  const bool operator < (str ult) const {
    if(b != ult.b) {
      return b < ult.b;
    }
    return a < ult.a;
  }
} v[nmax];
 
bool f[nmax];
 
int32_t main() {
  int n, ult = -1, ok = 1;
  cin >> n;
  set<str> ms;
  for(int i = 1; i <= n; i ++) {
    cin >> v[i].a >> v[i].b;
    if(ult != -1 && v[i].b != ult) {
      ok = 0;
    }
    ult = v[i].b;
  }
  if(ok == 1) {
    int ans = 0;
    sort(v + 1, v + n + 1);
    for(int i = 1; i <= n; i ++) {
      if(v[i].a != v[i - 1].a) {
        ans ++;
      }
    }
    cout << ans;
    return 0;
  }
  for(int i = 1; i <= n; i ++) {
    ms.insert({v[i].a, v[i].b});
  }
  int ans = 0;
  while(!ms.empty()) {
    auto it = ms.rbegin();
    ans ++;
    int ita = (*it).a, itb = (*it).b;
    for(int i = 1; i <= n; i ++) {
      if(!f[i] && abs(v[i].a - ita) <= itb - v[i].b) {
        f[i] = 1;
        if(ms.find({v[i].a, v[i].b}) != ms.end()) {
          ms.erase({v[i].a, v[i].b});
        }
      }
    }
  }
  cout << ans;
  return 0;
}

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