Submission #743793

#	Time	Username	Problem	Language	Result	Execution time	Memory
743793		vjudge1	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	424 ms	79824 KiB

Main

#include<bits/stdc++.h>

using namespace std;

int n,x,y;
stack<pair<int, int>> s;

inline void read(int &x)
{
    x = 0;
    char ch = getchar_unlocked();
    while (ch & 16)
    {
        x = (x << 3) + (x << 1) + (ch & 15);
        ch = getchar_unlocked();
    }
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    read(n);
    for(int i = 0; i<n; ++i){
        read(x); read(y);
        if(!s.empty() && abs(s.top().first-x)<=s.top().second-y){
            continue;
        }
        while(!s.empty() && abs(x-s.top().first)<=y-s.top().second) s.pop();
        s.push({x,y});
    }
    cout<<s.size();
}

• 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