Submission #1307552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307552		aryan	Inspections (NOI23_inspections)	C++20	55 / 100	2096 ms	13336 KiB

Main

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

const int N = 2e5;
vector<int> tree(4 * N,0);
vector<bool> lazy(4 * N,false);

void dolazy(int ind,int l,int r){
    int mid = (l + r) / 2;
    if(lazy[ind]){
        tree[2 * ind] = mid - l + 1;
        tree[2 * ind + 1] = r - mid;
        lazy[2 * ind] = lazy[2 * ind + 1] = true; 
    }
    lazy[ind] = false;
}

void update(int ind,int nl,int nr,int l,int r){
    if(l > nr || nl > r){
        return;
    }
    // l nl  nr r
    if(nl >= l && nr <= r){
        tree[ind] = nr - nl + 1;
        lazy[ind] = true;
        return;
    }
    assert(nl != nr);
    dolazy(ind,nl,nr);
    int mid = (nl + nr) / 2;
    update(2 * ind,nl,mid,l,r);
    update(2 * ind + 1,mid + 1,nr,l,r);
    tree[ind] = tree[2 * ind] + tree[2 * ind + 1];
}

int query(int ind,int nl,int nr,int l,int r){
    if(l > nr || nl > r){
        return 0;
    }
    if(nl >= l && nr <= r){
        return tree[ind];
    }
    assert(nl != nr);
    dolazy(ind,nl,nr);
    int mid = (nl + nr) / 2;
    return query(2 * ind,nl,mid,l,r) + query(2 * ind + 1,mid + 1,nr,l,r);
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m,q;
    cin >> n >> m >> q;
    vector<int> l(m),r(m);
    for(int i = 0;i < m;i++){
        cin >> l[i] >> r[i];
        l[i] --;
        r[i] --;
    }
    vector<pair<i64,int>> s(q);

    for(int i = 0;i < q;i++){
        cin >> s[i].first;
        s[i].second = i;
    }
    sort(s.begin(),s.end());

    function<pair<int,int>(int,int,int,int)> ins = [&](int l1,int r1,int l2,int r2){
        if(l1 > l2){
            swap(l2,l1);
            swap(r1,r2);
        }
        // l1 r1 l2 r2
        if(l2 > r1) return pair<int,int>{-1,-1};
        return pair<int,int>{l2,min(r1,r2)};
    };

    // for(int i = 0;i < q;i++){
    //     cout << s[i].first << " " << s[i].second << '\n';
    // }

    vector<i64> val(q + 1);
    for(int i = m - 1;i >= 0;i--){
        tree = vector<int>(4 * N,0);
        lazy = vector<bool>(4 * N,false);
        int ml = l[i];
        int mr = r[i];
        i64 tot = 0;
        for(int j = i - 1;j >= 0;j--){
            int yl = l[j];
            int yr = r[j];
            pair<int,int> pi = ins(ml,mr,yl,yr);
            // update(1,0,n - 1,)
            if(pi.first != -1){
                int cur = query(1,0,n - 1,pi.first,pi.second);
                int my = pi.second - pi.first + 1 - cur;
                i64 res = tot + pi.first - ml - pi.first + yr;
                assert(my >= 0 && res >= 0);
                int idx = lower_bound(s.begin(),s.end(),pair<i64,int>{res + 1,-1}) - s.begin();
                idx --;
                // int s1 = 0;
                // int e1 = q - 1;
                // while(e1 > s1){
                //     int mid = (s1 + e1 + 1) / 2;
                //     if(s[mid].first < res){
                //         s1 = mid;
                //     }else{
                //         e1 = mid - 1;
                //     }
                // }
                if(idx >= 0) val[idx] += my;
                // cout << i << " " << j << " " << res << " " << my << " " << idx << '\n';
                // cout << i << " " << j << " "  << idx << " " << res <<  '\n';
             }
             update(1,0,n - 1,yl,yr);
             tot += yr - yl + 1;
             // 3 (6) 10
             // 5 (6) 8
             // l1 .... pl ... r1
             // l2 ..... pl .... r2
        }
    }

    for(int i = q - 1;i >= 0;i--){
        val[i] += val[i + 1];
    }
    vector<i64> ans(q);
    for(int i = 0;i < q;i++){
        ans[s[i].second] = val[i];
    }
    for(int i = 0;i < q;i++){
        cout << ans[i] << " ";
    }
    cout << '\n';
    return 0;
}

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