Submission #515940

#	Time	Username	Problem	Language	Result	Execution time	Memory
515940		Joo	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	1851 ms	192504 KiB

Main

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



int main(void){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    stack<pair<int, int>> st;

    for(int i = 1; i <= n; i++){
        int x, y; cin >> x >> y;
        while(!st.empty() and x-st.top().first <= y-st.top().second) st.pop();
        if(st.empty() or (x-st.top().first > y-st.top().second and x-st.top().first > st.top().second-y)) st.push({x, y});
    }

    cout << st.size();

    return 0;
}

• 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: 20 / 20