#include"bits/stdc++.h"
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,n) for(ll i=0;i<(ll)n;++i)
#define rep3(i,l,r) for(ll i=(ll)l;i<(ll)r;++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)a-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
static constexpr ll mod1=998244353;
static constexpr ll mod=1000000007;
static constexpr ll inf=numeric_limits<ll>::max()/2;
using vl=vector<ll>;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,m,q;cin>>n>>m>>q;
vl l(m),r(m);
rep(i,m)cin>>l[i]>>r[i];
for(auto&e:l)e--;
vl s(q);
for(auto&e:s)cin>>e;
vl idx(q);iota(all(idx),0);
sort(all(idx),[&](ll i,ll j){return s[i]>s[j];});
map<ll,ll>cnt;
set<array<ll,3>>st;
st.insert({0,n,-1});
ll now=0;
rep(i,m){
ll tmp=l[i];
auto it=st.lower_bound({l[i],-1,-1});
if(it!=st.begin()){
auto pit=prev(it);
auto prev=*pit;
if(prev[1]>l[i]){
ll lt=prev[2];
if(prev[1]<=r[i]){
if(lt!=-1){
lt+=l[i]-prev[0];
cnt[now-lt]+=prev[1]-l[i];
}
now+=prev[1]-l[i];
st.erase(pit);
st.insert({prev[0],l[i],prev[2]});
tmp=prev[1];
}
else{
if(lt!=-1){
lt+=l[i]-prev[0];
cnt[now-lt]+=r[i]-l[i];
}
now+=r[i]-l[i];
st.erase(pit);
st.insert({prev[0],l[i],prev[2]});
st.insert({r[i],prev[1],prev[2]});
tmp=r[i];
}
}
}
while(tmp<r[i]&&it!=st.end()){
auto prev=*it;
if(prev[0]>=r[i])break;
assert(prev[0]==tmp);
if(prev[1]<=r[i]){
it=st.erase(it);
if(prev[2]!=-1)cnt[now-prev[2]]+=prev[1]-prev[0];
tmp=prev[1];
now+=prev[1]-prev[0];
}
else{
it=st.erase(it);
if(prev[2]!=-1)cnt[now-prev[2]]+=r[i]-prev[0];
tmp=r[i];
now+=r[i]-prev[0];
st.insert({r[i],prev[1],prev[2]});
}
}
assert(tmp==r[i]);
st.insert({l[i],r[i],now-(r[i]-l[i])});
//cerr<<now<<endl;
}
ll sum=0;
vl ans(q);
for(auto id:idx){
while(cnt.size()&&(prev(cnt.end())->first)>s[id]){
sum+=prev(cnt.end())->second;
cnt.erase(prev(cnt.end()));
}
ans[id]=sum;
}
rep(i,q){
cout<<ans[i];
if(i!=q-1)cout<<" ";
else cout<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
