Submission #1262549

#TimeUsernameProblemLanguageResultExecution timeMemory
1262549phtungLightning Rod (NOI18_lightningrod)C++20
0 / 100
1004 ms263072 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; int l = p[0].first, r = p.back().first; auto check = [&](int x, int y) -> bool{ auto [i, j] = st.top(); int x1 = max(l, x - y), y1 = min(r, x + y); int x2 = max(l, i - j), y2 = min(r, i + j); if(x1 == x2 && y1 == y2) return y >= j; if( x1 <= x2 && y1 >= y2 ) return true; return false; }; for(int i = 0; i < p.size(); i++) { auto [x, y] = p[i]; bool ok = 0; while(true) { if(st.size()) { if(check(x, y)) { ok = 1; st.pop(); } else break; } else break; } 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...