# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1225620 | TadijaSebez | Advertisement 2 (JOI23_ho_t2) | C++20 | 365 ms | 30088 KiB |
#include <bits/stdc++.h>
using namespace std;
const int N=500050;
int x[N],e[N],ord[N];
bool done[N];
int main(){
int n;
scanf("%i",&n);
set<pair<int,int>> all;
for(int i=1;i<=n;i++){
scanf("%i %i",&x[i],&e[i]);
if(all.count({x[i],e[i]})){
n--;
i--;
}else{
all.insert({x[i],e[i]});
ord[i]=i;
}
}
sort(ord+1,ord+1+n,[&](int i,int j){return x[i]<x[j];});
int ans=0;
int mx=e[ord[1]]+x[ord[1]];
for(int i=2;i<=n;i++){
if(e[ord[i]]+x[ord[i]]<=mx){
done[i]=true;
}
mx=max(mx,e[ord[i]]+x[ord[i]]);
}
mx=e[ord[n]]-x[ord[n]];
for(int i=n-1;i>=1;i--){
if(e[ord[i]]-x[ord[i]]<=mx){
done[i]=true;
}
mx=max(mx,e[ord[i]]-x[ord[i]]);
}
for(int i=1;i<=n;i++){
if(!done[i])ans++;
}
printf("%i\n",ans);
return 0;
}
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... |