| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1150593 | zjjws | Inspections (NOI23_inspections) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
// #define LL __int128_t
#define LL long long
const int Rea=1e5+3;
bool ifnum(char x){return x>='0'&&x<='9';}
bool ifupchr(char x){return x>='A'&&x<='Z';}
bool iflochr(char x){return x>='a'&&x<='z';}
bool ifchr(char x){return x=='('||x==')'||x=='['||x==']'||ifnum(x)||ifupchr(x)||iflochr(x);}
struct Rin
{
char c;
char gc()
{
static char rea[Rea];
static char *head,*tail;
return head==tail&&(tail=(head=rea)+fread(rea,1,Rea,stdin)
,head==tail)?EOF:*head++;
}
Rin&operator >>(int &x)
{
bool tag=false;x=0;
for(c=gc();!ifnum(c);c=gc())if(c=='-'){c=gc();tag=true;break;}
for(;ifnum(c);c=gc())x=(x<<1)+(x<<3)+(c^'0');if(tag)x=-x;return *this;
}
Rin&operator >>(LL &x)
{
bool tag=false;x=0;
for(c=gc();!ifnum(c);c=gc())if(c=='-'){c=gc();tag=true;break;}
for(;ifnum(c);c=gc())x=(x<<1)+(x<<3)+(c^'0');if(tag)x=-x;return *this;
}
Rin&operator >>(char &x)
{
for(c=gc();!ifchr(c);c=gc());
x=c;
return *this;
}
Rin&operator >>(string &x)
{
x.clear();
for(c=gc();!ifchr(c);c=gc());
for(;ifchr(c);c=gc())x.push_back(c);
return *this;
}
}rin;
const int N=2e5+3;
int n,m,q;
map<LL,LL>val;
#define ls (i<<1)
#define rs (i<<1|1)
struct node
{
int l,r;
bool iftag;
LL tag;
vector<LL>tim;
node(){l=r=0;iftag=false;tag=0;}
node(int l,int r,bool iftag,LL tag):l(l),r(r),iftag(iftag),tag(tag){}
void adtag(LL tag_)
{
if(iftag)val[tag_-tag-1]+=r-l+1;
tag=tag_;
iftag=1;
}
}t[N<<2];
void down(int i)
{
if(t[i].iftag)
{
t[ls].adtag(t[i].tag);
t[rs].adtag(t[i].tag);
t[i].iftag=0;
}
return;
}
void maketree(int l,int r,int i)
{
t[i]=node(l,r,false,0);
if(l==r)return;
int mid=l+r>>1;
maketree(l,mid,ls);
maketree(mid+1,r,rs);
return;
}
void cover(int l,int r,int i,int ql,int qr,LL qv)
{
if(ql<=l&&r<=qr)
{
// t[i].adtag(qv);
t[i].tim.push_back(qv);
return;
}
int mid=l+r>>1;
// down(i);
if(ql<=mid)cover(l,mid,ls,ql,qr,qv);
if(mid<qr)cover(mid+1,r,rs,ql,qr,qv);
return;
}
void alldown(int l,int r,int i)
{
if(l==r)return;
int mid=l+r>>1;
down(i);
alldown(l,mid,ls);
alldown(mid+1,r,rs);
return;
}
unordered_set<LL>timed;
void insert(LL p,int lens)
{
// for(auto tl:timed)printf("%lld ",tl); printf(" insert %lld ",p);puts("");
if(!timed.empty())
{
auto it=timed.upper_bound(p),jt=it;
if(it==timed.end())
{
jt--;
val[p-(*jt)-1]+=lens;
}
else if(it==timed.begin())
{
val[(*it)-p-1]+=lens;
}
else
{
jt--;
val[(*it)-(*jt)-1]-=lens;
val[p-(*jt)-1]+=lens;
val[(*it)-p-1]+=lens;
}
}
timed.insert(p);
return;
}
void erase(LL p,int lens)
{
// if(!timed.empty())
// {
// auto it=timed.upper_bound(p),jt=timed.find(p);
// if(it==timed.end())
// {
// jt--;
// val[p-(*jt)-1]-=lens;
// }
// else if(it==timed.begin())
// {
// val[(*it)-p-1]-=lens;
// }
// else
// {
// jt--;
// val[(*it)-(*jt)-1]+=lens;
// val[p-(*jt)-1]-=lens;
// val[(*it)-p-1]-=lens;
// }
// }
timed.erase(timed.find(p));
return;
}
void checkall(int l,int r,int i)
{
// printf("check [%d,%d]\n",l,r);
for(auto timed:t[i].tim)insert(timed,r-l+1);
if(l==r){for(auto timed:t[i].tim)erase(timed,r-l+1);return;}
int mid=l+r>>1;
checkall(l,mid,ls);
checkall(mid+1,r,rs);
for(auto timed:t[i].tim)erase(timed,r-l+1);
return;
}
int L;
LL key[N<<6];
LL sum[N<<6];
void print(__int128_t x)
{
static int lens;
static int num[256];
lens=0;
for(;x>0;x/=10)num[++lens]=x%10;
if(lens==0)num[++lens]=0;
for(;lens>0;lens--)putchar('0'+num[lens]);
return;
}
void que(LL s)
{
int l=1,r=L;
LL ans=0;
for(;l<=r;)
{
int mid=l+r>>1;
if(key[mid]<s)ans=sum[mid],l=mid+1;
else r=mid-1;
}
printf("%lld",sum[L]-ans);
// print(sum[L]-ans);
if(q!=1)putchar(' ');
return;
}
int main()
{
rin>>n>>m>>q;
maketree(1,n,1);
LL tim=1;
for(;m-->0;)
{
int l,r;rin>>l>>r;
cover(1,n,1,l,r,tim-l);
tim+=(r-l+1);
}
// alldown(1,n,1);
checkall(1,n,1);
for(auto [u,v]:val)
{
// printf("[%lld %lld]",u,v);
key[++L]=u;
sum[L]=sum[L-1]+v;
}
// puts("");
for(;q>0;q--)
{
LL s;rin>>s;
que(s);
}
return 0;
}
/*
6 6 11
1 6
1 5
1 4
1 3
1 2
1 1
0 1 2 3 4 5 6 7 8 9 10
*/