思路:差分
数据范围比较大,所以考虑把数据离散化掉,因为我们只在意相对大小,不在意具体数值。
对于符号是 . 则cnt[pos]++,cnt[pos+1]--
对于符号是 + 则cnt[0]++,cnt[pos]--
对于符号是 - 则cnt[pos+1]++
然后前缀和一下,更新最值即可。
这样子你会发现过了80%的数据,还有20%的数据过不了(你猜我怎么知道的)
考虑一下这样的情况
5-
8+
显然答案取6或者7,结果是2最大。
如果按照上述方式,因为离散化后,5是1,8是2,其实答案可以是5到8之间的数字,但离散化后,我们就把这一段区间的数字都忽略掉了。
所以离散化出来的pos,只需要pos*=2即可,这样扩大了相邻两个数之间的间隔(保证两个数离散化后的之间起码有一个空)
然后就可以ac了
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define x first
#define y second
pair<int,char> a[1000005];
int b[1000005];
int cnt[1000105];
signed main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
b[i]=a[i].x;
}
sort(b+1,b+1+n);
int m=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++){
int pos=lower_bound(b+1,b+m+1,a[i].x)-b;
pos*=2;
if(a[i].y=='.'){
cnt[pos]++;
cnt[pos+1]--;
}
else if(a[i].y=='+'){
cnt[0]++,cnt[pos]--;
}
else{
cnt[pos+1]++;
}
}
int ans=cnt[0];
for(int i=1;i<=200005;i++){
cnt[i]+=cnt[i-1];
ans=max(ans,cnt[i]);
}
cout<<ans<<endl;
return 0;
}
京公网安备 11010502036488号