Submission #548730

#	Time	Username	Problem	Language	Result	Execution time	Memory
548730		jack715	Lightning Rod (NOI18_lightningrod)	C++14	80 / 100	2016 ms	262144 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second

using namespace std;

bool protect(pair<int, int>& a, pair<int, int>& b) {
    return (abs(a.ff-b.ff) <= a.ss-b.ss);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, a, b, ans = 1;
    cin >> n;
    stack<pair<int, int> > select;
    vector<pair<int, int> > nums(n), prot(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i].ff >> nums[i].ss;
        prot[i] = nums[i];
    }
    
    select.push(nums[0]);
    for (int i = 1; i < n; i++) {
        if (!select.empty() && protect(select.top(), nums[i]))
            continue;
        while (!select.empty() && protect(nums[i], select.top())) {
            ans--;
            select.pop();
        }
        ans++;        
        select.push(nums[i]);
    }

    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

lightningrod.cpp: In function 'int main()':
lightningrod.cpp:18:12: warning: unused variable 'a' [-Wunused-variable]
   18 |     int n, a, b, ans = 1;
      |            ^
lightningrod.cpp:18:15: warning: unused variable 'b' [-Wunused-variable]
   18 |     int n, a, b, ans = 1;
      |               ^

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