Submission #1311675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311675		aryan	Lightning Rod (NOI18_lightningrod)	C++20	66 / 100	1101 ms	195304 KiB

Main

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

 
template <class T>
struct fenwick_ma{
    int n;
    vector<T> tree;
    fenwick_ma(int _n){
        n = _n;
        tree = vector<T>(n,-1);
    }
    
    void update(int i,T v){
        for(;i < n;i |= (i + 1)){
            tree[i] = max(tree[i],v);
        }
    }
    T query(int i){
        T ans = -1;
        for(;i >= 0;i = (i & (i + 1)) - 1){
            ans = max(ans,tree[i]);
        }
        return ans;
    }
};

template <class T>
struct fenwick_mi{
    int n;
    vector<T> tree;
    fenwick_mi(int _n){
        n = _n;
        tree = vector<T>(n,INT_MAX);
    }
    
    void update(int i,T v){
        for(;i >= 0;i = (i & (i + 1)) - 1){
            tree[i] = min(tree[i],v);
        }
    }
    T query(int i){
        T ans = INT_MAX;
        for(;i < n;i |= (i + 1)){
            ans = min(ans,tree[i]);
        }
        return ans;
    }
};

int main(){
        
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<pair<int,int>> a(n);
    vector<int> su(n),di(n);
    for(int i = 0;i < n;i++){
        cin >> a[i].first >> a[i].second;
        su[i] = a[i].first + a[i].second;
        di[i] = a[i].first - a[i].second;
    }
    vector<int> ind(n);
    iota(ind.begin(),ind.end(),0);
    sort(ind.begin(),ind.end(),[&](int i,int j){
        return a[i].second < a[j].second;
    });

    int ans = 0;
    vector<pair<int,int>> ma,mi;
    fenwick_ma<int> fma(n + 1);
    fenwick_mi<int> fmi(n + 1);
    for(int i = n - 1;i >= 0;i--){
        bool ok = false;
        int e = ind[i];
        // for(pair<int,int> p : ma){
        //     if(p.first <= a[e].first){
        //         if(p.second >= su[i]) ok = true;
        //     }
        // }
        // for(pair<int,int> p : mi){
        //     if(p.first >= a[e].first){
        //         if(p.second <= di[e]) ok = true;
        //     }
        // }
        int maxi = fma.query(e - 1);
        int mini = fmi.query(e + 1);
        // cout << e << " " << maxi << " " << mini << '\n';
        if(maxi >= su[e]) ok = true;
        if(mini <= di[e]) ok = true;
        if(!ok){
            // ma.push_back({a[e].first,su[e]});
            // mi.push_back({a[e].first,di[e]});
            fma.update(e,su[e]);
            fmi.update(e,di[e]);
            ans ++;
        }
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 26 / 26
• Subtask 6: 0 / 10
• Subtask 7: 0 / 20