Submission #1150593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150593		zjjws	Inspections (NOI23_inspections)	C++20	Compilation error	0 ms	0 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;
#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
*/

Compilation message (stderr)

Main.cpp: In function 'void insert(long long int, int)':
Main.cpp:122:23: error: 'class std::unordered_set<long long int>' has no member named 'upper_bound'
  122 |         auto it=timed.upper_bound(p),jt=it;
      |                       ^~~~~~~~~~~
Main.cpp:125:13: error: 'jt' was not declared in this scope; did you mean 't'?
  125 |             jt--;
      |             ^~
      |             t
Main.cpp:134:13: error: 'jt' was not declared in this scope; did you mean 't'?
  134 |             jt--;
      |             ^~
      |             t