Submission #1039974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039974		TAhmed33	Advertisement 2 (JOI23_ho_t2)	C++98	100 / 100	1932 ms	156568 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 25;
const ll inf = 1e16;
#define mid ((l + r) >> 1)
#define tl (node << 1)
#define tr (node << 1 | 1)
struct SegmentTree1 {
    pair <ll, ll> tree[MAXN << 1];
    void update (int l, int r, int a, ll b, int node) {
        if (l > a || r < a) return;
        if (l == r) {
            tree[node] = {b, l};
            return;
        }
        update(l, mid, a, b, tl); update(mid + 1, r, a, b, tr);
        tree[node] = max(tree[tl], tree[tr]);
    }
    pair <ll, ll> get (int l, int r, int a, int b, int node) {
        if (l > b || r < a) return {-inf, 0};
        if (l >= a && r <= b) return tree[node];
        return max(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
    }
} cur1;
struct SegmentTree2 {
    pair <ll, ll> tree[MAXN << 1];
    void update (int l, int r, int a, ll b, int node) {
        if (l > a || r < a) return;
        if (l == r) {
            tree[node] = {b, l};
            return;
        }
        update(l, mid, a, b, tl); update(mid + 1, r, a, b, tr);
        tree[node] = min(tree[tl], tree[tr]);
    }
    pair <ll, ll> get (int l, int r, int a, int b, int node) {
        if (l > b || r < a) return {inf, 0};
        if (l >= a && r <= b) return tree[node];
        return min(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
    }
} cur2;
array <ll, 2> a[MAXN];
int n;
bool vis[MAXN];
vector <int> topo;
int f[MAXN], g[MAXN];
void dfs (int pos) {
    vis[pos] = 1;
    cur1.update(1, n, pos, -inf, 1);
    cur2.update(1, n, pos, inf, 1);
    while (true) {
        auto x = cur1.get(1, n, 1, f[pos], 1);
        if (x.first < a[pos][0] - a[pos][1]) {
            break;
        }
        dfs(x.second);
    }
    while (true) {
        auto x = cur2.get(1, n, g[pos], n, 1);
        if (x.first > a[pos][0] + a[pos][1]) {
            break;
        }
        dfs(x.second);
    }
    topo.push_back(pos);
}
int comp[MAXN];
void dfs2 (int pos, int c) {
    comp[pos] = c; vis[pos] = 1;
    cur1.update(1, n, pos, -inf, 1);
    cur2.update(1, n, pos, inf, 1);
    while (true) {
        auto x = cur1.get(1, n, 1, f[pos], 1);
        if (x.first < a[pos][0] + a[pos][1]) {
            break;
        }
        dfs2(x.second, c);
    }
    while (true) {
        auto x = cur2.get(1, n, g[pos], n, 1);
        if (x.first > a[pos][0] - a[pos][1]) {
            break;
        }
        dfs2(x.second, c);
    }
}
vector <int> occ[MAXN];
void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1];
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        int l = 1, r = n, ans = -1;
        while (l <= r) {
            if (a[mid][0] >= a[i][0]) {
                ans = mid; r = mid - 1; 
            } else {
                l = mid + 1;
            }
        }
        g[i] = ans; 
        l = 1, r = n, ans = -1;
        while (l <= r) {
            if (a[mid][0] <= a[i][0]) {
               ans = mid; l = mid + 1; 
            } else {
                r = mid - 1;
            }
        }
        f[i] = ans;
    }
/*    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            if (abs(a[i][0] - a[j][0]) <= a[i][1] - a[j][1]) {
                cout << i << " " << j << '\n';
            }
        }
    }*/
    for (int i = 1; i <= n; i++) {
        cur1.update(1, n, i, a[i][0] - a[i][1], 1);
        cur2.update(1, n, i, a[i][0] + a[i][1], 1);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    reverse(topo.begin(), topo.end());
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) {
        cur1.update(1, n, i, a[i][0] + a[i][1], 1);
        cur2.update(1, n, i, a[i][0] - a[i][1], 1);
    }
    int cnt = 0;
    for (auto i : topo) {
        if (!vis[i]) {
            dfs2(i, ++cnt);
        }
    }
    for (int i = 1; i <= n; i++) {
        occ[comp[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        cur1.update(1, n, i, a[i][0] + a[i][1], 1);
        cur2.update(1, n, i, a[i][0] - a[i][1], 1);
    }
    int ans = 0;
    for (int i = 1; i <= cnt; i++) {
        for (auto j : occ[i]) {
            cur1.update(1, n, j, -inf, 1);
            cur2.update(1, n, j, inf, 1); 
        }
        bool flag = 0;
        for (auto j : occ[i]) {
            auto x = cur1.get(1, n, 1, f[j], 1);
            if (x.first >= a[j][0] + a[j][1]) {
                flag = 1; break;
            }
            auto y = cur2.get(1, n, g[j], n, 1);
            if (y.first <= a[j][0] - a[j][1]) {
                flag = 1; break;
            }
        }
        if (!flag) {
            ans++;
        }
        for (auto j : occ[i]) {
            cur1.update(1, n, j, a[j][0] + a[j][1], 1);
            cur2.update(1, n, j, a[j][0] - a[j][1], 1); 
        }
    }
    cout << ans << '\n';
}       
signed main () {
    ios::sync_with_stdio(0); cin.tie(0);
    int tc = 1; //cin >> tc;
    while (tc--) solve();
}

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