Submission #496830

#TimeUsernameProblemLanguageResultExecution timeMemory
496830SirCovidThe19thLightning Rod (NOI18_lightningrod)C++17
100 / 100
1918 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, x, y) for (int i = x; i < y; i++) #define pii pair<int, int> #define f first #define s second int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; bool covered[n] = {}; pii A[n]; stack<pii> S; FOR(i, 0, n){ cin >> A[i].f >> A[i].s; while (!S.empty() and S.top().f >= A[i].f - A[i].s){ covered[S.top().s] = 1; S.pop(); } S.push({A[i].f - A[i].s, i}); } S = stack<pii>(); for (int i = n - 1; ~i; i--) if (!covered[i]){ while (!S.empty() and S.top().f <= A[i].f + A[i].s){ covered[S.top().s] = 1; S.pop(); } S.push({A[i].f + A[i].s, i}); } cout<<n - accumulate(covered, covered + n, 0)<<endl; }
#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...