Submission #992035

#	Time	Username	Problem	Language	Result	Execution time	Memory
992035		ThMinh_	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	178 ms	19908 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, ans, inf;

struct rei {
   int x, e, pos;
};
rei a[N];

void init() {
   cin >> n;
   for(int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].e;
}

struct bit {
   int tr[N];

   void up(int x, int val) {
      while(x) {
         tr[x] = max(tr[x], val);
         x -= x & -x;
      }
   }

   int get(int x) {
      int res = inf;
      while(x <= n) {
         res = max(res, tr[x]);
         x += x & -x;
      }
      return res;
   }
} f, l;

int main () {
   cin.tie(0) -> sync_with_stdio(0);
   if(fopen("Task.inp", "r")) {
      freopen("Task.inp", "r", stdin);
      freopen("WA.out", "w", stdout);
   }

   inf = - 2e9;
   init();

   sort(a + 1, a + n + 1, [] (rei x, rei y) {
      return x.x < y.x;
   });
   for(int i = 1; i <= n; ++i) a[i].pos = i;

   sort(a + 1, a + n + 1, [] (rei x, rei y) {
      return x.e > y.e;
   });

   fill(f.tr + 1, f.tr + n + 1, inf);
   fill(l.tr + 1, l.tr + n + 1, inf);

   for(int i = 1; i <= n; ++i) {
      bool ok = 1;
      if(a[i].pos - 1) ok &= (f.get(n + 2 - a[i].pos) < a[i].e + a[i].x);
      if(n - a[i].pos) ok &= (l.get(a[i].pos + 1) < a[i].e - a[i].x);
      ans += ok;

      f.up(n - a[i].pos + 1, a[i].e + a[i].x);
      l.up(a[i].pos, a[i].e - a[i].x);
   }

   cout << ans;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:39:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |       freopen("Task.inp", "r", stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:40:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |       freopen("WA.out", "w", stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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