Submission #890696

#	Time	Username	Problem	Language	Result	Execution time	Memory
890696		Marco_Escandon	Advertisement 2 (JOI23_ho_t2)	C++11	100 / 100	1004 ms	72788 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(15);
#pragma GCC optimize("Ofast")
typedef long long ll;
struct Segment_Tree{
    typedef long long ll;
    vector<ll>  ST;
    Segment_Tree(ll n){
        ST.assign(2*(n+1),-1e17);
    }
    void update(ll a, ll b){
        a+=ST.size()/2; ST[a]=b;
        for(a/=2; a>0; a=a/2)
            ST[a]=max(ST[a*2],ST[a*2+1]);
    }
    ll RMQ(ll a, ll b)
    {
        a += ST.size()/2; b += ST.size()/2;
        ll s = -1e17;
        while (a <= b) {
            if (a%2 == 1) s = max(s,ST[a++]);
            if (b%2 == 0) s = max(s,ST[b--]);
            a /= 2; b /= 2;
        }
        return s;
    }
};
int main()
{
    ll n;
    cin>>n;
    vector<pair<ll,ll>> v(n),v2(n);
    Segment_Tree l(n+2),r(n+2);
    for(int i=0; i<n; i++){
        cin>>v[i].second>>v[i].first;
        v2[i].first=v[i].second;
        v2[i].second=v[i].first;
    }
    sort(v.begin(),v.end());reverse(v.begin(),v.end());sort(v2.begin(),v2.end());
    map<pair<ll,ll>, ll> mapa;
    for(int i=0; i<n; i++)
    {
        swap(v2[i].first,v2[i].second);
        mapa[v2[i]]=i+1;
    }
    ll cont=0;
    for(int i=0; i<n; i++)
    {  		 if(l.RMQ(1,mapa[v[i]])>=v[i].second+v[i].first||r.RMQ(mapa[v[i]],n)>=v[i].first-v[i].second);
        else cont++;
        l.update(mapa[v[i]],v[i].second+v[i].first);
        r.update(mapa[v[i]],v[i].first-v[i].second);
    }
    cout<<cont;
    return 0;
}

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