Submission #544692

#TimeUsernameProblemLanguageResultExecution timeMemory
544692AbdelmagedNourLightning Rod (NOI18_lightningrod)C++17
100 / 100
1829 ms242120 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; const int N=10000005; int n,a[N],b[N],nxta[N]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=0;i<n;i++){ int x,y; cin>>x>>y; a[i]=y-x; b[i]=y+x; } stack<int>st; for(int i=n-1;i>=0;i--){ while(!st.empty()&&a[st.top()]<a[i])st.pop(); nxta[i]=(st.empty()?-1:st.top()); st.push(i); } int res=0,pos=0,mx=INT_MIN; while(pos<n){ if(b[pos]<=mx){ pos++; continue; } res++; while(nxta[pos]!=-1)pos=nxta[pos]; mx=max(mx,b[pos]); } cout<<res; 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...