#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n,m,q;
cin>>n>>m>>q;
set<tuple<int,int,ll>> ranges;
vector<pair<ll,ll>> v;
ll x=0;
forn(i,m){
int l,r;
cin>>l>>r;
--l,--r;
auto it=ranges.lower_bound({l+1,0,0LL});
if(it!=begin(ranges)){
auto[s,e,y]=*prev(it);
if(s<=l&&l<=e){
ll first=y+l-s;
v.eb(x-first-1,min(r,e)-l+1);
ranges.erase(prev(it));
if(s<l) ranges.emplace(s,l-1,y);
if(r<e) ranges.emplace(r+1,e,y+r+1-s);
}
}
it=ranges.lower_bound({l+1,0,0LL});
while(it!=end(ranges)){
auto[s,e,y]=*it;
if(s>r) break;
ll first=x+s-l;
v.eb(first-y-1,min(r,e)-s+1);
it=ranges.erase(it);
if(r<e){
ranges.emplace(r+1,e,y+r+1-s);
break;
}
}
ranges.emplace(l,r,x);
x+=r-l+1;
}
sort(all(v));
forn(i,sz(v)-1) v[i+1].snd+=v[i].snd;
forn(i,q){
ll s; cin>>s;
int lo=-1,hi=sz(v);
while(hi-lo>1){
int mid=(lo+hi)/2;
if(v[mid].fst>=s) hi=mid;
else lo=mid;
}
ll res=v[sz(v)-1].snd-(lo==-1?0:v[lo].snd);
cout<<res<<' ';
}
cout<<'\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |