思路:差分
数据范围比较大,所以考虑把数据离散化掉,因为我们只在意相对大小,不在意具体数值。
对于符号是 . 则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; }