Submission #837980

#	Time	Username	Problem	Language	Result	Execution time	Memory
837980		gun_gan	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	346 ms	29968 KiB

Main

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

const int MX = 5e5 + 5;

int X[MX], E[MX];
int N;

int getId(int x) {
      auto it = lower_bound(X + 1, X + 1 + N, x) - X;
      return it;
}

struct stMin {
      int t[4 * MX];

      void update(int v, int l, int r, int pos, int val) {
            if(pos > r || pos < l) return;
            if(l == r) {
                  t[v] = min(t[v], val);
                  return;
            }
            int mid = (l + r) >> 1;
            update(v * 2 + 0, l, mid + 0, pos, val);
            update(v * 2 + 1, mid + 1, r, pos, val);
            t[v] = min(t[v * 2 + 0], t[v * 2 + 1]);
      }

      int query(int v, int l, int r, int ql, int qr) {
            if(qr < l || ql > r) return 2e9;
            if(ql <= l && qr >= r) return t[v];
            int mid = (l + r) >> 1;
            return min(query(v * 2 + 0, l, mid + 0, ql, qr), 
                  query(v * 2 + 1, mid + 1, r, ql, qr));
      }
} st;

struct stMax {
      int t[4 * MX];

      void update(int v, int l, int r, int pos, int val) {
            if(pos > r || pos < l) return;
            if(l == r) {
                  t[v] = max(t[v], val);
                  return;
            }
            int mid = (l + r) >> 1;
            update(v * 2 + 0, l, mid + 0, pos, val);
            update(v * 2 + 1, mid + 1, r, pos, val);
            t[v] = max(t[v * 2 + 0], t[v * 2 + 1]);
      }

      int query(int v, int l, int r, int ql, int qr) {
            if(qr < l || ql > r) return 0;
            if(ql <= l && qr >= r) return t[v];
            int mid = (l + r) >> 1;
            return max(query(v * 2 + 0, l, mid + 0, ql, qr), 
                  query(v * 2 + 1, mid + 1, r, ql, qr));
      }
} tt;

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

      for(int i = 0; i < 4 * MX; i++) st.t[i] = 2e9;

      cin >> N;
      vector<pair<int,int>> v;
      for(int i = 1; i <= N; i++) {
            cin >> X[i] >> E[i];
            v.push_back({E[i], X[i]});
      }

      sort(X + 1, X + 1 + N);

      sort(v.rbegin(), v.rend());

      int ans = 0;

      for(auto [e, x] : v) {
            if(st.query(1, 1, N, getId(x), N) <= x - e) continue;
            if(tt.query(1, 1, N, 1, getId(x)) >= x + e) continue;
            st.update(1, 1, N, getId(x), x - e);
            tt.update(1, 1, N, getId(x), x + e);
            ans++;
      }

      cout << ans << '\n';
}

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