Submission #696817

#	Time	Username	Problem	Language	Result	Execution time	Memory
696817		tsumondai	Lightning Rod (NOI18_lightningrod)	C++14	100 / 100	1982 ms	262144 KiB

Main

#include<bits/stdc++.h>
using namespace std;
stack<pair<int, int>> stk;
vector<pair<int, int>> temp;

int main() {
    cin.tie(0)->sync_with_stdio(false);
    //freopen("thunder.inp", "r", stdin);
    //freopen("thunder.out", "w", stdout);
    int n;
	cin >> n;
	for (int i=1; i<=n; i++) {
        int x,y;
        cin >> x >> y;
        temp.push_back({x,y});
	}
	sort(temp.begin(), temp.end());
	for (int i=0; i<n; i++) {
		int x,y;
		x=temp[i].first; y=temp[i].second;
		if(stk.empty()) stk.push({x, y});
		else
		{
			int h = stk.top().second - x + stk.top().first;
			if(h >= y) continue ;
			while(!stk.empty())
			{
				int h = y - x + stk.top().first;
				if(h >= stk.top().second) stk.pop();
				else break ;
			}
			stk.push({x, y});
		}
	}
	cout << stk.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