This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
//x - l_i + p_{i-1} - p_j + r_j - x
//(p_{i-1} - l_i) + (r_j - p_j) > s is the condition
//only r_j - p_j is important
struct range
{
ll l,r,val = -1e18;
range(){}
range(ll _l,ll _r,ll _val){
l = _l;
r = _r;
val = _val;
}
friend bool operator<(const range &a,const range &b){
return b.r > a.r;
}
};
set<range>s;
int main()
{
owo
int n,m,q;
cin>>n>>m>>q;
vector<PII>p(m),qs;
vector<ll>pref(m,0);
for(int i=0;i<m;i++){
cin>>p[i].fi>>p[i].se;
pref[i] = p[i].se - p[i].fi+1;
if(i)pref[i]+=pref[i-1];
}
for(int i=0;i<q;i++){
int x;
cin>>x;
qs.pb({x,i});
}
sort(all(qs));
vector<ll>ans(q,0);
s.insert(range(1,n,-1e18));
for(int i=0;i<m;i++){
ll l0 = p[i].fi;
ll r0 = p[i].se;
vector<range>add;
add.pb(range(l0,r0,r0 - pref[i]));
while(true){
auto it = s.ub(range(0,l0-1,0)); //first guy with r >= l0
if(it == s.end())break;
if(it->l > r0)break;
if(it->l < l0)add.pb(range(it->l,l0-1,it->val));
if(it->r > r0)add.pb(range(r0+1,it->r,it->val));
ll inter = min(r0,it->r) - max(l0,it->l)+1;
ll gap = (i?pref[i-1]:0) - l0 + it->val + 1;
//cout<<"gap "<<inter<<" "<<gap<<'\n';
int idx = lb(all(qs),make_pair(gap,0LL)) - qs.begin()-1;
if(idx>=0)ans[idx] += inter;
s.erase(it);
}
for(auto x:add)s.insert(x);
/*
cout<<"at "<<i<<'\n';
for(auto x:s){
cout<<x.l<<" "<<x.r<<" "<<x.val<<'\n';
}*/
}
for(int i=q-2;i>=0;i--)ans[i]+=ans[i+1];
vector<ll>fin(q);
for(int i=0;i<q;i++)fin[qs[i].se] = ans[i];
for(int i=0;i<q;i++)cout<<fin[i]<<" ";
cout<<'\n';
}
# | 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... |