Submission #1118588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118588		sitablechair	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	1969 ms	77484 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=5e5+3;

int n,p[N];
pair<int,int> a[N];
set<pair<int,int>> an,cut;
struct SegTree { 
    bool rizz=0;
    pair<int,int> tr[N*4];
    pair<int,int> merge(const pair<int,int> a, const pair<int,int> b) {
        if (rizz==0 || a.ff!=b.ff) return max(a,b);
        return min(a,b);
    } 
    void build(int id,int l,int r,pair<int,int> *src) {
        if (l==r) return void(tr[id]={(rizz==0)?src[l].ss-src[l].ff:src[l].ss+src[l].ff,l});
        int mid=l+r>>1;
        build(id*2,l,mid,src);
        build(id*2+1,mid+1,r,src);
        tr[id]=merge(tr[id*2],tr[id*2+1]);
    }
    void update(int id,int l,int r,int u) {
        if (l>u || r<u) return;
        int mid=l+r>>1;
        if (l==r) return void(tr[id]={(int)(-2e9),0});
        update(id*2,l,mid,u);
        update(id*2+1,mid+1,r,u);
        tr[id]=merge(tr[id*2],tr[id*2+1]);
    } 
    pair<int,int> query(int id,int l,int r,int u,int v) {
        if (l>v || r<u) return {(int)(-2e9),0};
        if (l>=u && r<=v) return tr[id];
        int mid=l+r>>1;
        return merge(query(id*2,l,mid,u,v),query(id*2+1,mid+1,r,u,v));
    }
} st,st1;

int solve(int l,int r) {
    if (l>r) return 0;
    int ans=2;
    pair<int,int> sus=st.query(1,1,n,l,r),sus1=st1.query(1,1,n,l,r);
    swap(sus.ff,sus.ss);
    swap(sus1.ff,sus1.ss);
    if (sus.ss<=-2e9) return 0;
    if (sus.ff+1>sus1.ff-1) {
        if (sus.ff==r || st1.query(1,1,n,sus.ff+1,r).ff<=a[sus.ff].ff+a[sus.ff].ss) return 1;
        if (sus1.ff==l || st.query(1,1,n,l,sus1.ff-1).ff<=a[sus1.ff].ss-a[sus1.ff].ff) return 1;
        return 2;
    }
    For(i,l,sus.ff) {
        if (an.find({a[i].ss-a[i].ff,i})!=an.end()) an.erase({a[i].ss-a[i].ff,i});
        if (cut.find({a[i].ss+a[i].ff,i})!=cut.end()) cut.erase({a[i].ss+a[i].ff,i});
    }
    For(i,sus1.ff,r) {
        if (an.find({a[i].ss-a[i].ff,i})!=an.end()) an.erase({a[i].ss-a[i].ff,i});
        if (cut.find({a[i].ss+a[i].ff,i})!=cut.end()) cut.erase({a[i].ss+a[i].ff,i});
    }
    if (sz(an)) {
        auto it=an.upper_bound({a[sus1.ff].ss-a[sus1.ff].ff,N+69});
        if (it!=an.begin()) {
            it=prev(it);
            while(it!=an.begin()) {
                int tmp=it->ss;
                it=prev(it);
                an.erase(next(it));
                cut.erase({a[tmp].ff+a[tmp].ss,tmp});
                st.update(1,1,n,tmp);
                st1.update(1,1,n,tmp);
            }
            int tmp=it->ss;
            an.erase(it);
            cut.erase({a[tmp].ff+a[tmp].ss,tmp});
            st.update(1,1,n,tmp);
            st1.update(1,1,n,tmp);
        }
    }
    if (sz(cut)) {
        auto it=cut.upper_bound({a[sus.ff].ss+a[sus.ff].ff,N+69});
        if (it!=cut.begin()) {
            it=prev(it);
            while(it!=cut.begin()) {
                int tmp=it->ss;
                it=prev(it);
                cut.erase(next(it));
                an.erase({a[tmp].ss-a[tmp].ff,tmp});
                st.update(1,1,n,tmp);
                st1.update(1,1,n,tmp);
            }
            int tmp=it->ss;
            cut.erase(it);
            an.erase({a[tmp].ss-a[tmp].ff,tmp});
            st.update(1,1,n,tmp);
            st1.update(1,1,n,tmp);
        }
    }
    ans+=solve(sus.ff+1,sus1.ff-1);
    return ans;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    For(i,1,n) cin >> a[i].ff >> a[i].ss;
    sort(a+1,a+1+n);
    st1.rizz=1;
    st.build(1,1,n,a);
    st1.build(1,1,n,a);
    For(i,1,n) {
        an.insert({a[i].ss-a[i].ff,i});
        cut.insert({a[i].ss+a[i].ff,i});
    }
    cout << solve(1,n) << endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void SegTree::build(int, int, int, std::pair<int, int>*)':
Main.cpp:39:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int mid=l+r>>1;
      |                 ~^~
Main.cpp: In member function 'void SegTree::update(int, int, int, int)':
Main.cpp:46:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         int mid=l+r>>1;
      |                 ~^~
Main.cpp: In member function 'std::pair<int, int> SegTree::query(int, int, int, int, int)':
Main.cpp:55:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int mid=l+r>>1;
      |                 ~^~

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