Submission #742950

#	Time	Username	Problem	Language	Result	Execution time	Memory
742950		Sainen420	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	1712 ms	94376 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using pi = pair<int,int>;

int xl,yl,x,y;
int ans=0,n;
stack<pi> s;
bool v=true;

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> x >> y;
        if(s.empty()){s.push({x,y});}
        v=true;
        while(true){
            if(s.empty())break;
            auto[xl,yl]=s.top();
            if(x-xl <= yl-y){//negative gradient = nom'd
                v=false;
                break;
            }
            if(x-xl <= y-yl){
                s.pop();
            }else{
                break;
            }
        }
        if(v)s.push({x,y});
    }
    cout << s.size();
    return 0;
}
/*
3
0 0
1 1
2 3
*/

• 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