TOI10: Treasure Chest

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long int ll;
struct mp{
    ll c2,c3,c5,c7;
};
mp Mplus(mp a,mp b){
    mp c;
    c.c2 = a.c2 + b.c2;
    c.c3 = a.c3 + b.c3;
    c.c5 = a.c5 + b.c5;
    c.c7 = a.c7 + b.c7;
    return c;
}
mp Mminus(mp a,mp b){
    mp c;
    c.c2 = a.c2 - b.c2;
    c.c3 = a.c3 - b.c3;
    c.c5 = a.c5 - b.c5;
    c.c7 = a.c7 - b.c7;
    return c;
}
mp ItM(ll x){
    mp ans = {0,0,0,0};
    ll arr[4] = {2,3,5,7};
    for(int i = 0 ; i < 4 ; i ++){
        while(x % arr[i] == 0){
            switch(arr[i]){
                case(2):{
                    ans.c2++;
                    break;
                }
                case(3):{
                    ans.c3++;
                    break;
                }
                case(5):{
                    ans.c5++;
                    break;
                }
                case(7):{
                    ans.c7++;
                    break;
                }
            }
            x/=arr[i];
        }
    }
    return ans;
}
struct elem{
    mp p;
    ll pos;
    int state;
};
bool mycmp(elem a,elem b){
    return a.pos < b.pos;
}
ll ctD(mp x){
    return (x.c2+1)*(x.c3+1)*(x.c5+1)*(x.c7+1);
}
int main(){
    ll m,n;
    scanf("%lld %lld",&m,&n);
    vector<elem> vec;
    for(int i = 0 ; i < m ; i ++){
        ll x,s,t;
        scanf("%lld %lld %lld",&x,&s,&t);
        vec.push_back({ItM(x),s,1});
        vec.push_back({ItM(x),t+1,-1});
    }
    sort(vec.begin(),vec.end(),mycmp);
    ll prevpos = 0; // (L,R]

    ll maxD = 0;
    ll ans = 0;
    mp now = {0,0,0,0};
    for(int i = 0 ; i < vec.size() ; i++){
        ll pos = vec[i].pos;
    //  printf("Test %lld\n",pos);
        mp p = vec[i].p;
        int state = vec[i].state;
        if(pos != prevpos){
            ll cD = ctD(now);
        //  printf("Test (%lld-%lld) %lld \n",prevpos,pos,cD);
            if(cD > maxD){
                ans = pos - prevpos;
                maxD = cD;
            }
            else if(cD == maxD){
                ans += pos - prevpos;
            }
        }
        if(state == 1){
            now = Mplus(now,p);
        }else{
            now = Mminus(now,p);
        }
        prevpos = pos;
    }
    printf("%lld %lld",maxD,ans);
    return 0;
}