815D - Karen and Cards - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

long long n,aa,bb,cc;
long long l1[500010],l2[500010],l3[500010],ans=0,sum[500010];
vector <pair <pair <long long,long long>,long long> > v;
int main()
{
  for(int i=0;i<500005;i++)
   l1[i]=l2[i]=l3[i]=1;
  cin>>n>>aa>>bb>>cc;
  long long  x,y,z;
  for(int i=0;i<n;i++)
  {
    scanf("%lld%lld%lld",&x,&y,&z);
       v.push_back(make_pair(make_pair(x,y),z));
    l1[x]=max(l1[x],y+1);l2[x]=max(l2[x],z+1);l3[y]=max(l3[y],z+1);
     
  }
  
  for(int i=500000;i>=0;--i) l1[i]=max(l1[i],l1[i+1]),l2[i]=max(l2[i],l2[i+1]),l3[i]=max(l3[i],l3[i+1]);
    for(int i=0;i<500001;i++) sum[i+1]=sum[i]+(cc-l3[i]+1); 
       for(int i=1;i<=aa;i++)
  {
    int leastb=l1[i],leastc=l2[i];
    int lb=leastb,ub=bb+1,mid;
    while(lb<ub)
    {
      mid=(lb+ub)/2;
      if(mid==bb+1||l3[mid]<=leastc) ub=mid;
      else lb=mid+1;
    }
    ans+=(bb-lb+1)*(cc-leastc+1);
    ans+=sum[lb]-sum[leastb];
  
  }
  cout<<ans<<endl;
  return 0;

}/*1694578089.663095*/