Submission #541688

#TimeUsernameProblemLanguageResultExecution timeMemory
541688cristi_aLightning Rod (NOI18_lightningrod)C++17
80 / 100
2023 ms262144 KiB
#include <bits/stdc++.h> using namespace std; bool cover(pair<int,int> a, pair<int,int> b) { return abs(a.first-b.first) <= a.second - b.second; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<pair<int,int>> v(n); for(int i=0; i<n; i++) cin >> v[i].first >> v[i].second; sort(v.begin(), v.end()); stack<pair<int,int>> st; for(int i=0; i<n; i++) { while(!st.empty() and cover(v[i], st.top())) st.pop(); if(st.empty()) st.emplace(v[i]); else if(!cover(st.top(), v[i])) st.emplace(v[i]); } cout << st.size(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...