#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
const int mxnode = 2e7+1,N = 2e5+1;
vi L(N), R(N), val(mxnode,-1);
vector<ll> s(N), sm(mxnode);
vector<pair<ll,int>> S;
int q;
void update(int v, int tl, int tr, int l, int r, ll Val){
if (tl==l && tr==r){
sm[v] += Val; return;
}
if (l>r) return;
int tm = (tl+tr)/2;
update(2*v,tl,tm,l,min(r,tm), Val);
update(2*v+1,tm+1,tr,max(l,tm+1),r,Val);
}
ll get(int v, int tl, int tr, int pos){
if (tl==tr) return sm[v];
int tm = (tl+tr)/2;
if (pos <= tm) return sm[v] + get(2*v,tl,tm,pos);
return sm[v] + get(2*v+1,tm+1,tr,pos);
}
void upd(int v, int tl, int tr, int l, int r, int ind){
if (tl != tr && val[v] != -1){
val[2*v]=val[2*v+1]=val[v];
}
if (l>r) return;
if (tl==l && tr==r && (tl==tr || val[v] != -1)){
if (val[v] != -1){
ll num = s[ind-1] + (l-L[ind]) - s[val[v]-1] - (l-L[val[v]]);
//cout<<val[v]<<" "<<ind<<" "<<num<<" "<<r-l+1<<"\n";
int pos = lower_bound(S.begin(), S.end(), make_pair(num,0)) - S.begin();
//cout<<pos<<" "<<num<<"\n";
update(1,0,q,0,pos-1,r-l+1);
}
val[v] = ind;
return;
}
int tm = (tl+tr)/2;
upd(2*v,tl,tm,l,min(r,tm),ind);
upd(2*v+1,tm+1,tr,max(l,tm+1),r,ind);
if (val[2*v] == val[2*v+1] && val[2*v] != -1) val[v]=val[2*v];
else val[v]=-1;
}
int main(){
int n, m; cin>>n>>m>>q;
FOR(i,1,m+1){
cin>>L[i]>>R[i];
}
//cout<<ndcnt<<"\n";
FOR(i,0,q){
ll val; cin>>val;
S.pb({val,i});
}
sort(S.begin(), S.end());
FOR(i,1,m+1){
upd(1,1,n,L[i],R[i],i);
s[i]=s[i-1]+(R[i]-L[i]+1);
}
vector<ll> ans(q);
FOR(i,0,q){
ans[S[i].se] = get(1,0,q,i);
}
FOR(i,0,q) cout<<ans[i]<<" ";
cout<< "\n";
return 0;
}
Compilation message
Main.c:1:10: fatal error: bits/stdc++.h: No such file or directory
1 | #include <bits/stdc++.h>
| ^~~~~~~~~~~~~~~
compilation terminated.
