Submission #1038245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038245		SoulKnight	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	227 ms	22480 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ln '\n'

const int N = 5e5 + 5;
array<int, 2> t[N];
int n, a[N], b[N], id[N];
// int id1[N], id2[N];
bool need[N];
priority_queue<int, vector<int>, greater<int>> pq;


void f(){
    while (!pq.empty()) pq.pop();

    for (int i = 0; i < n; i++){
        while (!pq.empty()){
            if (pq.top() > id[i]) break;
            // dsu.unite(pq.top(), id[i]);
            need[abs(pq.top())] = 0;
            pq.pop();
        }
        pq.push(id[i]);
    }
}

void solve(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> t[i][0] >> t[i][1];
    sort(t, t+n);
    auto x = unique(t, t+n);
    n = distance(t, x);

    for (int i = 0; i < n; i++){
        a[i] = t[i][1] - t[i][0];
        b[i] = t[i][1] + t[i][0];
    }

    // iota(id1, id1+n, 0); iota(id2, id2+n, 0);
    // sort(id1, id1+n, [&](int x, int y){return a[x] == a[y]? x < y: a[x] < a[y];});
    // sort(id2, id2+n, [&](int x, int y){return b[x] == b[y]? x > y: b[x] < b[y];});
    // // reverse(id2, id2+n);
    // for (int i = 0; i < n; i++) cout << id1[i] << ' ';
    // cout << ln;
    // for (int i = 0; i < n; i++) cout << id2[i] << ' ';

    for (int i = 0; i < n; i++) need[i] = 1;
    iota(id, id+n, 0);
    sort(id, id+n, [&](int x, int y){return a[x] == a[y]? x < y: a[x] < a[y];});
    f();

    iota(id, id+n, 0);
    sort(id, id+n, [&](int x, int y){return b[x] == b[y]? x > y: b[x] < b[y];});
    for (int i = 0; i < n; i++) id[i] = -id[i];
    f();

    cout << accumulate(need, need+n, 0) << ln;


}

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

    // ll TT; cin >> TT;
    // while (TT--) {solve();}

    solve();

}

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