Submission #1311672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311672		aryan	Lightning Rod (NOI18_lightningrod)	C++20	40 / 100	1102 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),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;
    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[e]) ok = true;
            }
        }
        for(pair<int,int> p : mi){
            if(p.first >= a[e].first){
                if(p.second <= di[e]) ok = true;
            }
        }
        if(!ok){
            ma.push_back({a[e].first,su[e]});
            mi.push_back({a[e].first,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: 0 / 26
• Subtask 6: 0 / 10
• Subtask 7: 0 / 20