SMMR-125: Infinite Array

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N = 100010;

ll L[N], R[N], X[N];
ll qs[2*N],qs2[2*N];

int main()
{
    ll n, m;
    scanf("%lld %lld", &n, &m);

    vector<ll> coord;
    coord.push_back(0);
    for (ll i = 1; i <= n; ++i) {
        scanf("%lld %lld %lld", &L[i], &R[i], &X[i]);
        coord.push_back(L[i]);
        coord.push_back(R[i]+1);
    }
    sort(coord.begin(), coord.end());
    coord.resize(unique(coord.begin(), coord.end())-coord.begin());

    for (ll i = 1; i <= n; ++i) {
        ll l = L[i], r = R[i], x = X[i];
        ll a = lower_bound(coord.begin(), coord.end(), l) - coord.begin();
        ll b = lower_bound(coord.begin(), coord.end(), r+1) - coord.begin();
        qs[a] += x;
        qs[b] -= x;
    }
    for (ll i = 1; i < coord.size(); ++i)
        qs[i] += qs[i-1];


    for(ll i=1;i<coord.size();i++){
        ll x = coord[i]-coord[i-1]-1; //printf("%d ",x);
        qs2[i]= (x*qs[i-1])+qs2[i-1] +qs[i];
    }//printf("\n");
/*for (int i = 0; i < coord.size(); ++i)
    printf("%d| %d\n",coord[i],qs2[i]);*/
    while (m--) {
        ll l, r;
        scanf("%lld %lld", &l, &r);

        ll a = upper_bound(coord.begin(), coord.end(), l)-1 - coord.begin();
        ll b = upper_bound(coord.begin(), coord.end(), r)-1 - coord.begin();
//printf("[%d %d]",coord[a],coord[b]);
        ll s1= qs2[a]+ ((l-coord[a])*qs[a]);
        ll s2= qs2[b]+ ((r-coord[b])*qs[b]);
//printf("[%d %d]",s1,s2);
        printf("%lld\n",s2-s1+qs[a]);
    }

    return 0;
}