Submission #1311379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311379		aryan	Lightning Rod (NOI18_lightningrod)	C++20	40 / 100	1101 ms	195292 KiB

Main

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

using i64 = long long;


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);
    vector<int> 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; 
    }

    // for(int i = 0;i < n;i++){
    //     cout << su[i] << " ";
    // }
    // cout << '\n';
    // for(int i = 0;i < n;i++){
    //     cout << di[i] << " ";
    // }
    // cout << '\n';

    su.push_back(-1);
    di.push_back(INT_MAX);
    vector<bool> is(n,false);
    vector<bool> bad(n,false);

    function<int(int,int)> f_ma = [&](int l,int r){
        if(l > r) return n;
        if(l < 0 || r > n) return n;
        int maxi = -1;
        int ind = n;
        for(int i = r;i >= l;i--){
            if(su[i] >= maxi && !bad[i]){
                ind = i;
                maxi = su[i];
            }
        }
        return ind;
    };

    function<int(int,int)> f_mi = [&](int l,int r){
        if(l > r) return n;
        if(l < 0 || r > n) return n;
        int maxi = INT_MAX;
        int ind = -1;
        for(int i = l;i <= r;i++){
            if(di[i] <= maxi && !bad[i]){
                ind = i;
                maxi = di[i];
            }
        }
        return ind;
    };

    int l = 0;
    int r = n - 1;
    // int ans = 0;
    bool d = false;
    while(r >= l){
        int nr = f_ma(l,r);
        int nl = f_mi(l,r);
        // cout << " " << l << " " << r << " " << nl << " " << nr << '\n';
        if(d){
            // int bma = f_ma(0,l - 1);
            // int fmi = f_mi(r + 1,n - 1); 
            int bma = n;
            int fmi = n;
            for(int i = 0;i <= l - 1;i++){
                if(su[nr] <= su[i]){
                    bma = i;
                    if(is[i]) break;
                }
            }
             for(int i = r + 1;i < n;i++){
                if(di[nl] >= di[i]){
                    fmi = i;
                    if(is[i]) break;
                }
            }
            if(su[nr] <= su[bma] && di[nl] >= di[fmi]){
                // ans ++;
                if(is[bma] || is[fmi]) break;
                is[bma] = true;
                break;
            }
            if(su[nr] <= su[bma]){
                is[bma] = true;
                break;
            }
            if(di[nl] >= di[fmi]){
                // ans ++;
                is[fmi] = true;
                break;
            }
        }
        d = true;
        if(nr == l || nl == r || nl == nr){
            // ans ++;
            if(nl == r){
                is[nl] = true;
            }else if(nr == l){
                is[nr] = true;
            }else{
                is[nl] = true;
            }
            break;
        }
        is[nl] = true;
        is[nr] = true;
        if(nl > nr) is[nl] = true;
        for(int i = 0;i < n;i++){
            if(a[nl].second - a[i].second >= abs(a[nl].first - a[i].first)){
                bad[i] = true;
            }
            if(a[nr].second - a[i].second >= abs(a[nr].first - a[i].first)){
                bad[i] = true;
            }
        }

        l = nl + 1;
        r = nr - 1;

    }
    int ans = 0;
    for(int i = 0;i < n;i++){
        if(is[i]) ans ++;
    }
    cout << ans << '\n';
    return 0;
}

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