提出 #76650757

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,xt;
int c[(int)2e6+10];
struct node{
  int x,y;
}a[(int)2e6+10];
int c1[(int)2e6+10];
void add(int x){
    int __=x;
  for(;x<=2000000;x+=(x&-x))c[x]+=__;
}
int query(int x){
  if(x==0)return 0;
  int res=0;
  for(;x;x-=(x&-x))res+=c[x];
  return res;
}
void add2(int x){
  for(;x<=2000000;x+=(x&-x))c1[x]++;
}
int query2(int x){
  if(x==0)return 0;
  int res=0;
  for(;x;x-=(x&-x))res+=c1[x];
  return res;
}
bool cmp(node x,node y){
  if(x.x==y.x)return x.y<y.y;
  return x.x<y.x;
}
signed main(){
  cin>>n>>xt;
  for(int i=1;i<=n;i++){
    cin>>a[i].x>>a[i].y;
  }
  sort(a+1,a+n+1,cmp);
  int res=0;
  for(int i=1;i<=n;i++){
    if(a[i].y-a[i].x>=xt){
    int d=query(((int)(2e6)))-query(a[i].x+xt-1);
    int d2=query2(((int)(2e6)))-query2(a[i].x+xt-1);
    int d3=query(((int)(2e6)))-query(a[i].y);
    int d4=query2(((int)(2e6)))-query2(a[i].y);
    d2=max(d2,0ll);
    d4=max(d4,0ll);
    d-=d3,d2-=d4;
    int ans=d-d2*a[i].x-d2*xt+d2;
    res+=ans;
    res+=((a[i].y-a[i].x)-xt+1)*d4;
    //cout<<ans<<' '<<((a[i].y-a[i].x)-xt+1)*d4<<'\n';
    }
    add(a[i].y);
    add2(a[i].y);
  }
  cout<<res;
  return 0;
}

提出情報

ジャッジ結果