今天解决了qdoj.club 1125 选择客栈
下面是我(因为数据过水而勉强通过的)代码:
#include <bits/stdc++.h>
using namespace std;long long n,k,t,p,a[200010],b[110][100010],c[110],v[200010],d[200010][20],ans;int main(){ cin>>n>>k>>p; for(int i=1;i<=n;i++){ cin>>v[i]>>a[i]; v[i]++; c[v[i]]++; b[v[i]][c[v[i]]]=i; d[i][0]=a[i]; } for(int j=1;(1<<j)<=n;j++){ for(int i=1;i+(1<<j)-1<=n;i++){ d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]); } } long long i1,j1; for(int e=1;e<=k;e++){ for(int i=1;i<c[e];i++){ for(int j=i+1;j<=c[e];j++){ i1=b[e][i]; j1=b[e][j]; t=log2(j1-i1+1); if(min(d[i1][t],d[j1-(1<<t)+1][t])<=p){ ans+=c[e]-j+1; break; } } } } cout<<ans; return 0;}注释?不存在的qwq