Submission #915664

#	Time	Username	Problem	Language	Result	Execution time	Memory
915664		berr	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	193 ms	33628 KiB

Main

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

#define int long long
const int mod = 1e9+7;



signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;

    vector<array<int, 2>> a(n);

    for(auto &[x, y]: a) cin >> x >> y;

    sort(a.begin(), a.end());
    vector<array<int, 3>> ar(n);
    for(int i=0; i<n; i++){
        ar[i] = {a[i][1], i, a[i][0]};
    }

    sort(ar.begin(), ar.end());
    reverse(ar.begin(), ar.end());
    
    vector<int> vis(n);
    int ans = 0;

    for(auto [x, y, z]: ar){
        if(vis[y]) continue;

        int l = y-1, r = y+1;
        ans++;
        while(r<n &&!vis[r] && abs(a[r][0]-z) <= x-a[r][1]){
            vis[r] = 1;
            r++;
        }

        while(l>=0 &&!vis[l] && abs(a[l][0]-z) <= x-a[l][1]){
            vis[l] = 1;
            l--;
        }
    }

    cout << ans;
}

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