Magnet PROG1029

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;

typedef struct{ // [l,r)
    ll l,r,cnt;
}lenght;

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

    vector<pll> vec;
    for(int i=0;i<m;i++){
        ll l,r;
        scanf("%lld %lld",&l,&r);
        vec.push_back({l,1});
        vec.push_back({l+r,-1});
    }
    sort(vec.begin(),vec.end());

    vector<lenght> ans;
    ll sum = 0;
    ll previndex = 1;
    vector<lenght> all;
    for(ll i = 0 ; i < vec.size() ; i ++){
        if(vec[i].first != previndex){
            all.push_back({previndex,vec[i].first,sum % 2});
            previndex = vec[i].first;
        }
        if(all.size() > 2){
            if(all[all.size() - 3].cnt == all[all.size() - 2].cnt){
                all[all.size() - 3].r = all[all.size() - 2].r;
                lenght temp = all[all.size() - 1];
                all.pop_back();
                all.pop_back();
                all.push_back(temp);
            }
        }
        sum += vec[i].second;
    }
    all.push_back({previndex,n + 1,sum % 2});
    ll index = 0;
    while(index + 1 < all.size()){
        if(all[index].cnt == all[index + 1].cnt){
            all[index].r = all[index+1].r;
            all.erase(all.begin() + index + 1);
        }
        else{
            index++;
        }
    }
    for(int i = 0 ; i < k ; i ++){
        ll q;
        scanf("%lld",&q);
        ll l = 0,r = all.size() - 1;
        while(l <= r){
            ll m = (l + r)/2;
            ll beg = all[m].l;
            ll end = all[m].r;
            if(beg <= q && q < end){
                printf("%lld\n",end - beg);
                break;
            }
            else if(q < beg){
                r = m - 1;
            }
            else if(q >= end){
                l = m + 1;
            }
        }
    }
    return 0;
}