Submission #1118694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118694		HuyAT	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	263 ms	14760 KiB

Main

#include<bits/stdc++.h>
#define newl '\n'

const int N = 5e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;

struct SegmentTree{
    std::vector<int> st;
    SegmentTree(int n) : st(n * 4 + 10,0){

    }
    void update(int l,int r,int pos,int val,int id = 1){
        if(l == r){
            st[id] = std::max(st[id],val);
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid){
            update(l,mid,pos,val,id << 1);
        }else{
            update(mid + 1,r,pos,val,id << 1 | 1);
        }
        st[id] = std::max(st[id << 1],st[id << 1 | 1]) ;
    }
    int query(int l,int r,int u,int v,int id = 1){
        if(u <= l && r <= v){
            return st[id];
        }
        int mid = (l + r) / 2;
        if(v <= mid){
            return query(l,mid,u,v,id << 1);
        }
        if(u > mid){
            return query(mid + 1,r,u,v,id << 1 | 1);
        }
        return std::max(query(l,mid,u,v,id << 1),query(mid + 1,r,u,v,id << 1 | 1));
    }
};
int n,id[N + 1];
std::pair<int,int> p[N + 1];
std::vector<int> c;

void readData(){
    std::cin >> n;
    for(int i = 1;i <= n;++i){
        int x,e;
        std::cin >> x >> e;
        p[i] = {x - e,x + e};
        c.emplace_back(p[i].first);
    }
    auto cmp = [&](std::pair<int,int> &lhs,std::pair<int,int> &rhs){
        return (lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second > rhs.second));
    };
    std::sort(p + 1,p + n + 1,cmp);
    std::sort(c.begin(),c.end());
    c.erase(std::unique(c.begin(),c.end()),c.end());
}
int get_id(int val){
    return std::lower_bound(c.begin(),c.end(),val) - c.begin() + 1;
}
void solve(){
    SegmentTree st(n);
    int ans = 0;
    for(int i = 1;i <= n;++i){
        int id = get_id(p[i].first);
        if(st.query(1,n,1,id) < p[i].second){
            ++ans;
        }
        st.update(1,n,id,p[i].second);
    }
    std::cout << ans;
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
    readData();
    solve();
    return 0;
}

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