Submission #1262516

#TimeUsernameProblemLanguageResultExecution timeMemory
1262516phtungLightning Rod (NOI18_lightningrod)C++20
0 / 100
1079 ms310856 KiB
#include <bits/stdc++.h> using namespace std; #define name "IO" #define int long long const int inf = 1e9; const int maxn = 1e7 + 5; int n; void solve() { cin >> n; vector<pair<int,int>> p; for(int i = 1; i <= n; i++) { int x, y; cin >> x >> y; p.push_back({x, y}); } stack<pair<int,int>> st; auto check = [&](int x, int y) -> bool{ auto [i, j] = st.top(); if( max(0ll,(x - y)) <= max(0ll,(i - j)) && min(inf,(x + y)) >= min(inf, (i + j))) return true; return false; }; for(int i = 0; i < p.size(); i++) { auto [x, y] = p[i]; bool ok = 1; while(st.size() && check(x, y)) { ok = 0; st.pop(); } if(st.empty() || ok) st.push({x, y}); } cout << st.size() << "\n"; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); clock_t start = clock(); int t = 1; while(t--) solve(); std::cerr << "Time: " << clock() - start << "ms\n"; 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...