# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
219595 | GioChkhaidze | Lightning Rod (NOI18_lightningrod) | C++14 | 778 ms | 236936 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
int getn() {
char ch = getchar_unlocked();
int ans = 0;
while(!isdigit(ch)) {
ch = getchar_unlocked();
}
while(isdigit(ch)) {
ans = ans * 10 + ch - '0';
ch = getchar_unlocked();
}
return ans;
}
main () {
n=getn();
for (int i=1; i<=n; i++) {
x=getn();
y=getn();
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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |