Submission #1281503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281503		nanaseyuzuki	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	166 ms	24148 KiB

Main

#include<bits/stdc++.h>

using  namespace std;
#define fi first
#define se second
#define pii pair<int, int>

const int mn = 5e5+5;
int n, m, k;
pii a[mn];
int val1[mn], val2[mn];
int q[mn];

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++){
        val1[i] = a[i].fi - a[i].se;
        val2[i] = a[i].fi + a[i].se;
        q[i] = 1;
    }
    priority_queue <pii, vector <pii>, greater<pii>> pq1;
    priority_queue <pii> pq;
    for(int i = 1; i <= n; i++){
        while(!pq.empty() && pq.top().fi >= val1[i]){
            pq.pop();
        }
        pq.push({val1[i], i});
        // cout << pq.size() << '\n';
    }
    vector <int> xet;
    while(pq.size()){
        xet.push_back(pq.top().se);
        pq.pop();
    }
    sort(xet.begin(), xet.end(), greater <int>());
    for(auto i : xet){
        while(!pq1.empty() && pq1.top().fi <= val2[i]){
            pq1.pop();
        }
        pq1.push({val2[i], i});
    }
    cout << (int)pq1.size();
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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