Submission #922995

#	Time	Username	Problem	Language	Result	Execution time	Memory
922995		Gromp15	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	479 ms	24308 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template <class T>
struct segtree {
    const int N; vector<T> tree;
    segtree(int n) : N(1<<(__lg(n)+1)), tree(2*N, -2e9) {}
    void update(int pos, T x) {
        for (int i = pos+N; i > 0; i >>= 1) ckmax(tree[i], x);
    }
    T query(int node, int nl, int nr, int ql, int qr) {
        if (ql > nr || qr < nl) return -2e9;
        if (ql <= nl && nr <= qr) return tree[node];
        int mid = (nl+nr)/2;
        return max(query(node*2, nl, mid, ql, qr), query(node*2+1, mid+1, nr, ql, qr));
    }
    T query(int l, int r) { return query(1, 0, N-1, l, r); }
};
template <class T>
struct segtree2 {
    const int N; vector<T> tree;
    segtree2(int n) : N(1<<(__lg(n)+1)), tree(2*N, 2e9) {}
    void update(int pos, T x) {
        for (int i = pos+N; i > 0; i >>= 1) ckmin(tree[i], x);
    }
    T query(int node, int nl, int nr, int ql, int qr) {
        if (ql > nr || qr < nl) return 2e9;
        if (ql <= nl && nr <= qr) return tree[node];
        int mid = (nl+nr)/2;
        return min(query(node*2, nl, mid, ql, qr), query(node*2+1, mid+1, nr, ql, qr));
    }
    T query(int l, int r) { return query(1, 0, N-1, l, r); }
};
void test_case() {
    int n; cin >> n;
    vector<ar<int, 2>> t(n);
    for (auto &x : t) cin >> x[0] >> x[1];
    sort(all(t));
    vector<int> idx(n);
    iota(all(idx), 0);
    sort(all(idx), [&](int x, int y) { return t[x][1] > t[y][1]; });
    int ans = 0;
    segtree<int> mx(n);
    segtree2<int> mn(n);
    for (int _i = 0; _i < n; _i++) {
        int i = idx[_i];
        ans += !((i+1 < n && mn.query(i+1, n-1) <= t[i][0]-t[i][1]) || (i && t[i][0]+t[i][1] <= mx.query(0, i-1)));
        mn.update(i, t[i][0]-t[i][1]);
        mx.update(i, t[i][0]+t[i][1]);
    }
    cout << ans << '\n';

}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}

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