Submission #1150608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150608		zjjws	Inspections (NOI23_inspections)	C++20	0 / 100	5 ms	9800 KiB

Main

#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;
vector<LL>inse[N];
vector<LL>eras[N];
void cover(int ql,int qr,LL qv)
{
    inse[ql].push_back(qv);
    eras[qr+1].push_back(qv);
    return;
}
set<LL>timed;

void insert(LL p,int lens)
{
    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;
}
int L;
LL key[N<<6];
LL sum[N<<6];

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;

    LL tim=1;
    for(;m-->0;)
    {
        int l,r;rin>>l>>r;
        cover(l,r,tim-l);
        tim+=(r-l+1);
    }

    for(int i=1;i<=n;i++)
    {
        for(auto p:eras[i])erase(p,n-i+1);
        for(auto p:inse[i])insert(p,n-i+1);
    }

    for(auto [u,v]:val)
    {
        key[++L]=u;
        sum[L]=sum[L-1]+v;
    }

    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