Submission #893326

#	Time	Username	Problem	Language	Result	Execution time	Memory
893326		vjudge1	Inspections (NOI23_inspections)	C++17	100 / 100	261 ms	31912 KiB

Main

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxn=3e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll s[maxn];
pli t[maxn];
ll q;
ll pre[maxn];
void update(ll x,ll v)
{
    //x++;
    ll cc=upper_bound(s+1,s+q+1,x)-s-1;
    pre[cc]+=v;
}
ll giao(ll i,ll j,ll l,ll r)
{
    return max(0ll,min(j,r)-max(i,l)+1);
}
ll n,m,x[maxn],y[maxn],r[maxn],tg[maxn],pos[maxn];

void solve()
{
    cin >> n >> m >> q;
    for(int i=1;i<=m;i++)
    {
        cin >> x[i] >> y[i];
    }
    for(int i=1;i<=q;i++)
    {
        cin >> s[i];
        t[i]={s[i],i};
    }
    sort(s+1,s+q+1);
    sort(t+1,t+q+1);
    set<ll>s;
    ll sum=0;
    for(int i=1;i<=m;i++)
    {
        auto it=s.lower_bound(x[i]);
        vector<ll>xoa;
        if(i>0) sum+=y[i-1]-x[i-1]+1;
        if(it!=s.begin())
        {
            it--;
            ll l=*it;
            if(r[l]>=x[i])
            {
                 ll cc=sum - (tg[l]+x[i]-l) -1;
                 update(cc,giao(x[i],y[i],l,r[l]));
                 ll luu=r[l];
                 r[l]=x[i]-1;
                 if(luu>y[i])
                 {
                    s.insert(y[i]+1);
                    s.insert(x[i]);
                    r[x[i]]=y[i];
                    tg[x[i]]=sum;
                    r[y[i]+1]=luu;
                    tg[y[i]+1]=tg[l]+(y[i]+1-l);
                    continue;
                 }
            }
            it++;
        }
        while(it!=s.end()&&(*it)<=y[i])
        {
            ll l=*it;
            ll cc=sum+l-x[i]-tg[l]-1;
            update(cc,giao(l,r[l],x[i],y[i]));
            xoa.pb(l);
            if(r[l]>y[i])
            {
                s.insert(y[i]+1);
                r[y[i]+1]=r[l];
                tg[y[i]+1]=tg[l]+(y[i]+1-l);
                break;
            }
            it++;
        }
        r[x[i]]=y[i];
        tg[x[i]]=sum;
        for(auto zz:xoa) s.erase(zz);
        s.insert(x[i]);
    }
    for(int i=q;i>=1;i--)
    {
        pre[i]+=pre[i+1];
        pos[t[i].se]=i;
    }
    for(int i=1;i<=q;i++)
    {
        cout << pre[pos[i]]<<' ';
    }
}
int main()
{
    fastio
    //freopen("c.INP","r",stdin);
    //freopen("c.OUT","w",stdout);
    solve();
}

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