#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define int long long
#define double long double
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=1e6+5;
const ll offset=2e5;
const ll blk=317;
const ll inf=1e9;
const int base =311;
const ll mod=998244353;
int n,m,q;
int l[maxn],r[maxn];
struct seg
{
int l,r,id;
bool operator <(const seg& o) const
{
return l< o.l;
}
};
set<seg> L;
set<seg>::iterator it1,it2;
int pre[maxn],res[maxn];
pii s[maxn];
int ans[maxn];
void sol() {
cin >> n>> m>> q;
for1(i,1,m)
{
cin >> l[i]>> r[i];
pre[i]=pre[i-1]+r[i]-l[i]+1;
}
for1(i,1,q) {cin >> s[i].fi;s[i].se=i;}
sort(s+1,s+1+q);
vector<seg> del,add;
for1(i,1,m)
{
it1=L.upper_bound({l[i],l[i]});
it2=L.upper_bound({r[i],r[i]});
add.pb({l[i],r[i],i});
// if (i==5)
// {
// for(auto x: L)
// {
// cerr<< x.l<<' '<<x.r<<' '<<x.id<<'\n';
// }
// }
if (it1==it2 && it2!=L.begin() && it1!=L.begin())
{
it1--;
it2--;
if (it1->l<=l[i] && it1->r>=r[i])
{
// if (i==4) cerr<< "asda\n";
del.pb(*it1);
if (it2->r> r[i]) add.pb({r[i]+1,it2->r,it2->id});
if (it1->l< l[i]) add.pb({it1->l,l[i]-1,it1->id});
int cnt=it1->r-l[i]+1;
int g=pre[i-1]-pre[it1->id]+r[it1->id]-l[i];
int x=upper_bound(s+1,s+1+q,make_pair(g,inf))-s-1;
res[x]+=cnt;
for(auto x:del) L.erase(x);
for(auto x:add) L.insert(x);
del.clear();
add.clear();
continue;
}
it1++;
it2++;
}
if (it1!=L.begin())
{
// if (i==3) cerr<< "duy lo\n";
it1--;
if (it1->l<=l[i] && it1->r>=l[i])
{
del.pb(*it1);
if (it1->l< l[i]) add.pb({it1->l,l[i]-1,it1->id});
int cnt=it1->r-l[i]+1;
int g=pre[i-1]-pre[it1->id]+r[it1->id]-l[i];
int x=upper_bound(s+1,s+1+q,make_pair(g,inf))-s-1;
res[x]+=cnt;
}
it1++;
}
if (it2!=L.begin())
{
it2--;
if (it2->l<=r[i] && it2->r>=r[i])
{
// if (i==3) cerr<< "duy lo\n";
del.pb(*it2);
if (it2->r> r[i]) add.pb({r[i]+1,it2->r,it2->id});
int cnt=r[i]-it2->l+1;
int g=pre[i-1]-pre[it2->id-1]+l[it2->id]-l[i]-1;
int x=upper_bound(s+1,s+1+q,make_pair(g,inf))-s-1;
res[x]+=cnt;
}
// it2++;
}
// ++it2;
// if (it2==it1)
while (it1!=it2)
{
int cnt=it1->r-it1->l+1;
// cerr<< it1->l<< ' '<<it1->r<<'\n';
int g=pre[i-1]-pre[it1->id-1]+l[it1->id]-l[i]-1;
int x=upper_bound(s+1,s+1+q,make_pair(g,inf))-s-1;
res[x]+=cnt;
del.pb(*it1);
++it1;
}
for(auto x:del) L.erase(x);
for(auto x:add) L.insert(x);
del.clear();
add.clear();
}
for2(i,n,1) res[i]+=res[i+1];
for1(i,1,q) ans[s[i].se]=res[i];
for1(i,1,q) cout << ans[i]<<' ';
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("paleta.inp","r",stdin);
// freopen("paleta.out","w",stdout);
int t=1;//cin >> t;
while (t--) {
sol();
}
}
/*
3 5 5
1 2
2 3
3 3
1 1
1 2
1 3 2 5 100
3 4 5
1 2
2 3
3 3
1 1
1 3 2 5 100
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
