Submission #1184892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184892		SalihSahin	Inspections (NOI23_inspections)	C++20	22 / 100	123 ms	17748 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define pb push_back
using namespace std;

const int inf = 1e9*2;
const int N = 2e5 + 20;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m, q;
    cin>>n>>m>>q;
    vector<int> l(m), r(m), pre(m+1);
    for(int i = 0; i < m; i++){
        cin>>l[i]>>r[i];
        pre[i+1] = pre[i] + (r[i] - l[i] + 1);
    }

    vector<pair<int, int> > query(q);
    for(int i = 0; i < q; i++){
        cin>>query[i].first;
        query[i].second = i;
    }

    set<array<int, 3> > ranges;
    vector<pair<int, int> > upd;

    for(int i = 0; i < m; i++){
        // set ve l, r matchlerine bak her biri için {x, y} = eğer ki s değeri x ten küçük eşitse cevap += y
        if(!ranges.size()){
            ranges.insert({l[i], r[i], i});
            continue;
        }

        vector<array<int, 3> > ekle, sil;

        auto k = ranges.lower_bound({l[i], 0, 0});
        if(k != ranges.begin()) k--;

        while(k != ranges.end() && (*k)[0] <= r[i]){
            bool kesis = 0;

            if((*k)[0] >= l[i] && (*k)[1] <= r[i]){ // icinde
                int kind = (*k)[2];
                int poskind = pre[kind] + ((*k)[0] - l[kind] + 1);
                int posi = pre[i] + ((*k)[0] - l[i] + 1);
                int dis = posi - poskind;
                upd.pb({dis, (*k)[1] - (*k)[0] + 1});
                kesis = 1;
            }
            if((*k)[0] < l[i] && (*k)[1] <= r[i]){ // sol tarafimda
                int kind = (*k)[2];
                int poskind = pre[kind] + (l[i] - l[kind] + 1);
                int posi = pre[i] + 1;
                int dis = posi - poskind;
                upd.pb({dis, (*k)[1] - l[i] + 1});
                ekle.pb({(*k)[0], l[i]-1, kind});
                kesis = 1;
            }
            if((*k)[0] >= l[i] && (*k)[1] > r[i]){ // sag tarafimda
                int kind = (*k)[2];
                int poskind = pre[kind] + ((*k)[0] - l[kind] + 1);
                int posi = pre[i] + ((*k)[0] - l[i] + 1);
                int dis = posi - poskind;
                upd.pb({dis, r[i] - (*k)[0] + 1});
                ekle.pb({r[i] + 1, (*k)[1], kind});
                kesis = 1;
            }

            if((*k)[0] < l[i] && (*k)[1] > r[i]){ // beni iceriyor
                int kind = (*k)[2];
                int poskind = pre[kind] + (l[i] - l[kind] + 1);
                int posi = pre[i] + 1;
                int dis = posi - poskind;
                upd.pb({dis, r[i] - l[i] + 1});

                ekle.pb({(*k)[0], l[i]-1, kind});
                ekle.pb({r[i] + 1, (*k)[1], kind});
                kesis = 1;
            }

            if(kesis) sil.pb(*k);
            k++;
        }
        ekle.pb({l[i], r[i], i});

        for(auto itr: sil){
            ranges.erase(ranges.find(itr));
        }
        for(auto itr: ekle){
            ranges.insert(itr);
        }

    }

    sort(upd.rbegin(), upd.rend());
    sort(query.rbegin(), query.rend());
    int cur = 0, updind = 0;
    vector<int> ans(q);
    for(auto itr: query){
        while(updind < upd.size() && upd[updind].first > itr.first){
            cur += upd[updind].second;
            updind++;
        }
        ans[itr.second] = cur;
    }

    for(int i = 0; i < q; i++){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}

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