Submission #1150572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150572		zjjws	Inspections (NOI23_inspections)	C++20	0 / 100	11 ms	25416 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define LL __int128_t
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;
    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);
        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;
}


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);

    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;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 23