MLE ,60 pts
查看原帖
MLE ,60 pts
796667
ZY_jiang楼主2024/10/16 13:07
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define ls u*2
#define rs u*2+1
const int N=500001;
struct tree{
	ll l,r,minn;
}tr[4*N];
struct node{
	ll col,pos;
}a[N];
vector<pair<ll,ll> > adj;
ll n,m,k,p,ans;
void pushup(ll u){
	tr[u].minn=min(tr[ls].minn,tr[rs].minn);
	return ;
}
void build(ll u,ll l,ll r){
	tr[u].l=l;
	tr[u].r=r;
	if(l>=r){
		tr[u].minn=a[l].pos;
		return ;
	}
	build(ls,l,(l+r)/2);
	build(rs,(l+r)/2+1,r);
	pushup(u);
}
ll memery(ll u,ll l,ll r){
	if(l<=tr[u].l&&tr[u].r<=r){
		return tr[u].minn;
	}
	ll res=INT_MAX;
	ll mid=(tr[u].l+tr[u].r)/2;
	if(l<=mid) res=min(res,memery(ls,l,r));
	if(r>mid) res=min(res,memery(rs,l,r));
	return res;
}
int main(){
	cin>>n>>k>>p;
	for(int i=1;i<=n;i++){
		cin>>a[i].col>>a[i].pos;
	}
	build(1,1,n);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(a[i].col==a[j].col){
				adj.push_back({i,j});
			}
		}
	}
	for(auto w:adj){
		ll v=w.first;
		ll u=w.second;
		if(memery(1,v,u)<=p) ans++;
	}
	cout<<ans;
	return 0;
}
2024/10/16 13:07
加载中...