제출 #736231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
736231		Cookie	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	397 ms	23216 KiB

Main

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");

#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;

const ll mod = 1e9 + 7;
const int mxn = 5e5, mxm = 1e5, sq = 400;
const int base = (1 << 18);
const ll inf = 1e9;
const ld pre = 1e-6;
int n;
pll p[mxn + 1];
bool ok[mxn + 1];
ll bit[mxn + 1], bit2[mxn + 1];
ll get(int p){
    ll ans = 3e9;
    while(p){
        ans = min(ans, bit[p]);
        p -= p & (-p);
    }
    return(ans);
}
void upd(int p, ll v){
    while(p <= n){
        bit[p] = min(bit[p], v);
        p += p & (-p);
    }
}
ll get2(int p){
    ll ans = -3e9;
    while(p){
        ans = max(ans, bit2[p]);
        p -= p & (-p);
    }
    return(ans);
}
void upd2(int p, ll v){
    while(p <= n){
        bit2[p] = max(bit2[p], v);
        p += p & (-p);
    }
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    vt<pll>p;
    vt<int>comp;
    forr(i, 0, n){
        int x, e; cin >> x >> e;
        p.pb({e, x});
        comp.pb(x);
    }
    sort(comp.begin(), comp.end());
    sort(p.begin(), p.end());
    for(int i = 1; i <= n; i++)bit[i] = 3e9;
    for(int i = n - 1; i >= 0; i--){
       
        int id = lower_bound(comp.begin(), comp.end(), p[i].se) - comp.begin() + 1;
        ll res = get(n - id + 1);  //cout << res << " ";
        if(res <= p[i].se - p[i].fi){
           
            ok[i] = 1;
        }
        upd(n - id + 1, p[i].se - p[i].fi);
    }
    
    for(int i = 1; i <= n; i++)bit2[i] = -3e9;
    for(int i = n - 1; i >= 0; i--){
        
        int id = lower_bound(comp.begin(), comp.end(), p[i].se) - comp.begin() + 1;
        ll res = get2(id); 
        if(res >= p[i].se + p[i].fi){
            ok[i] = 1;
        }
        upd2(id, p[i].se + p[i].fi);
    }
    
    int ans = 0;
    forr(i, 0, n){
        ans += (!ok[i]);
    }
    cout << ans;
    return(0);
}

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