Submission #219589

#TimeUsernameProblemLanguageResultExecution timeMemory
219589GioChkhaidzeLightning Rod (NOI18_lightningrod)C++14
80 / 100
2086 ms118524 KiB
#include <bits/stdc++.h> using namespace std; const int N=1e7+7; bool f[N]; int n,x,y,X[N],Y[N],st[N],sts; inline void fastscan(int &number) { register int c; number = 0; c = getchar(); for (; (c>47 && c<58); c=getchar()) number = number *10 + c - 48; } main () { fastscan(n); for (int i=1; i<=n; i++) { fastscan(x); fastscan(y); X[i]=x-y; Y[i]=x+y; } for (int i=1; i<=n; i++) { if (sts) { while (sts && X[st[sts]]>=X[i]) { f[st[sts]]=1; --sts; } } st[++sts]=i; } sts=0; for (int i=n; i>=1; i--) { if (f[i]) continue; if (sts) { while (sts && Y[st[sts]]<=Y[i]) { --sts; } } st[++sts]=i; } cout<<sts; }

Compilation message (stderr)

lightningrod.cpp:15:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
#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...