Submission #1364477

#TimeUsernameProblemLanguageResultExecution timeMemory
1364477baoquanAdvertisement 2 (JOI23_ho_t2)C++20
100 / 100
102 ms16444 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pa pair<int, int>
#define tup tuple<int, int, int>
#define db double
#define fi first
#define se second
#define ull unsigned long long

const int maxn = 1e6 + 4, INF = 1e17 + 4, lg = 17, base = 31, mod = 1e9 + 7;

int n;
deque <pa> dq;
vector <pa> a;

void nhap()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1 ; i <= n ; i ++)
    {
        int x , e;
        cin >> x >> e;
        a.push_back({x - e , x + e});
    }
}

bool cmp(pa a , pa b)
{
    if (a.fi == b.fi)
        return a.se > b.se;
    return a.fi < b.fi;
}

bool check(pa x , pa y)
{
    return x.fi <= y.fi && y.se <= x.se;
}

void Solve()
{
    int ans = 0;
    for (auto [l , r] : a)
    {
        if (!dq.empty() && dq.front().se < l)
        {
            pa tmp = dq.front();
            while (!dq.empty() && check(tmp , dq.front()))
                dq.pop_front();
            ans ++;
        }
        dq.push_back({l , r});
    }
    while (!dq.empty())
    {
        pa tmp = dq.front();
        while (!dq.empty() && check(tmp , dq.front()))
            dq.pop_front();
        ans ++;
    }
    cout << ans << '\n';
}

signed main()
{
    nhap();
    sort(a.begin() , a.end() , cmp);
    // for (auto [pos , i] : p)
    //     cout << pos << ' ' << i << '\n';
    Solve();
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...