10WA求助
查看原帖
10WA求助
857323
linxuanrui楼主2023/2/13 15:48
#pragma GCC optmize(2)
#include<iostream>
using namespace std;
const int N = 200001;
int f[N][30],log[N],n,a[N],b[N],num[51][N],len[51],q,k,p,sum;
void init(int n){
	log[0] = -1;
	for(int i = 1;i <= n;i++)f[i][0] = b[i],log[i] = log[i >> 1] + 1;
	for(int j = 1;j <= log[n];j++){
		for(int i = 1;i + (1 << j) - 1 <= n;i++){
			f[i][j] = min(f[i][j - 1],f[i + (1 << (j - 1))][j - 1]);
		}
	}
}
int ask(int l,int r){
	int k = log[r - l + 1];
	return min(f[l][k],f[r - (1 << k) + 1][k]);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k >> p;
	for(int i = 1;i <= n;i++){
		cin >> a[i] >> b[i];
		num[a[i]][++len[a[i]]] = i;
	}
	init(n); 
	for(int i = 0;i < k;i++){
		for(int j = 1;j < len[i];j++){
			int l = j + 1,r = len[i] + 1;
			while(r - l > 1){
				int mid = (l + r) >> 1;
				if(ask(num[i][j],num[i][mid]) <= p)l = mid;
				else r = mid;
			}
			sum += (l == len[i] + 1 || ask(num[i][j],num[i][l]) > p ? 0 : l - j);
		}
	}
	cout << sum;
}
2023/2/13 15:48
加载中...