Submission #893378

#	Time	Username	Problem	Language	Result	Execution time	Memory
893378		damwuan	Inspections (NOI23_inspections)	C++17	0 / 100	1 ms	8540 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define int long long
#define double long double
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=1e6+5;
const ll offset=2e5;
const ll blk=317;
const ll inf=1e9;
const int base =311;
const ll mod=998244353;
int n,m,q;
int l[maxn],r[maxn];
struct seg
{
    int l,r,id;
    bool operator <(const seg& o) const
    {
        return l< o.l;
    }
};
set<seg> L;
set<seg>::iterator it1,it2;
int pre[maxn],res[maxn];
pii s[maxn];
int ans[maxn];
void sol() {
    cin >> n>> m>> q;
    for1(i,1,m)
    {
        cin >> l[i]>> r[i];
        pre[i]=pre[i-1]+r[i]-l[i]+1;
    }
    for1(i,1,q) {cin >> s[i].fi;s[i].se=i;}
    sort(s+1,s+1+q);
    vector<seg> del,add;
    for1(i,1,m)
    {
        it1=L.upper_bound({l[i],l[i]});
        it2=L.upper_bound({r[i],r[i]});
//        if (i==3)
//        {
//            for(auto x: L)
//            {
//                cerr<< x.l<<' '<<x.r<<' '<<x.id<<'\n';
//            }
//        }
        if (it1==it2 && it2!=L.begin() && it1!=L.begin())
        {
            it1--;
            it2--;
            if (it1->l<=l[i] && it1->r>=r[i])
            {
                int cnt=it1->r-l[i]+1;
                int g=pre[i-1]-pre[it1->id]+r[it1->id]-l[i];
                int x=upper_bound(s+1,s+1+q,make_pair(g,inf))-s-1;
                res[x]+=cnt;
                continue;
            }
            it1++;
            it2++;
        }
        add.pb({l[i],r[i],i});
        if (it1!=L.begin())
        {
//            if (i==3) cerr<< "duy lo\n";
            it1--;
            if (it1->l<=l[i] && it1->r>=l[i])
            {
                del.pb(*it1);
                if (it1->l< l[i]) add.pb({it1->l,l[i]-1,it1->id});
                int cnt=it1->r-l[i]+1;
                int g=pre[i-1]-pre[it1->id]+r[it1->id]-l[i];
                int x=upper_bound(s+1,s+1+q,make_pair(g,inf))-s-1;
                res[x]+=cnt;
            }
            it1++;
        }
        if (it2!=L.begin())
        {
            it2--;
            if (it2->l<=r[i] && it2->r>=r[i])
            {
//            if (i==3) cerr<< "duy lo\n";
                del.pb(*it2);
                if (it2->r> r[i]) add.pb({r[i]+1,it2->r,it2->id});
                int cnt=r[i]-it2->l+1;
                int g=pre[i-1]-pre[it2->id-1]+l[it2->id]-l[i]-1;
                int x=upper_bound(s+1,s+1+q,make_pair(g,inf))-s-1;
                res[x]+=cnt;

            }
//            it2++;
        }
//        ++it2;
//        if (it2==it1)
        while (it1!=it2)
        {
            int cnt=it1->r-it1->l+1;
//            cerr<< it1->l<< ' '<<it1->r<<'\n';
            int g=pre[i-1]-pre[it1->id-1]+l[it1->id]-l[i]-1;
            int x=upper_bound(s+1,s+1+q,make_pair(g,inf))-s-1;
            res[x]+=cnt;
            del.pb(*it1);
            ++it1;

        }
        for(auto x:del) L.erase(x);
        for(auto x:add) L.insert(x);
        del.clear();
        add.clear();

    }
    for2(i,n,1) res[i]+=res[i+1];
    for1(i,1,q) ans[s[i].se]=res[i];
    for1(i,1,q) cout << ans[i]<<' ';

}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("paleta.inp","r",stdin);
//    freopen("paleta.out","w",stdout);

    int t=1;//cin >> t;
    while (t--) {
        sol();
    }
}

/*
5 2 7
1 3
3 5
0 1 2 3 4 5 6
*/

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