题意
有$n$个客栈，每个客栈都配有咖啡馆。有两名旅客想住在同色调的客栈中，又想在两客栈之间的咖啡馆中小聚，咖啡馆的价钱不能高于$p$。 对于 $100\%$ 的数据，有 $2\leq n\leq2\times 10^6$，$0<k\leq10^4$ ，$0\leq p\leq100$，$0\leq$ 最低消费 $\leq100$ 。
思路
$n$的范围那么大，$k$的范围那么小。那么暴力吧。 设$h_i$表示目前颜色$i$的客栈数量，$las_i$表示最近的颜色为$i$的客栈的编号。 然后$O(n)$扫一遍就好了啊。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cstring>
#include<cmath>
#define ll long long
const int N=2e5+5,M=1e6;
using namespace std;
inline ll read(){
char ch=getchar();ll res=0,f=1;
while(ch<'0'ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
return res*f;
}
inline void write(ll zx){
if(zx<0) zx=-zx,putchar('-');
if(zx<10) putchar(zx+'0');
else{
write(zx/10);
putchar(zx%10+'0');
}
}
ll n,m,color,price,now,las[N],h[N],sum[N],ans,p;
int main(){
n=read();m=read();p=read();
for(ll i=1;i<=n;i++){
color=read(),price=read();
if(price<=p) now=i;
if(now>=las[color]) sum[color]=h[color];
ans+=sum[color];
h[color]++;las[color]=i;
}
write(ans);putchar('\n');
return 0;
}
|