Submission #832683

#	Time	Username	Problem	Language	Result	Execution time	Memory
832683		Liudas	Inspections (NOI23_inspections)	C++17	22 / 100	659 ms	32500 KiB

Main

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#define int long long
using namespace std;
struct seg{
    int l;
    int r;
    int time;
    bool operator<(const seg &a)const{
        return l < a.l;
    }
};
signed main(){
    int N, Q, M;
    cin >> N >> M >> Q;
    vector<seg> arr(M);
    int day = 0;
    for(int i = 0; i < M; i ++){
        int a, b;
        cin >> a >> b;
        arr[i] = {a,b,day};
        day += b-a+1;
    }
    map<int, int> vals;
    set<seg> in;
    for(int i = 0; i < M; i ++){
        seg a = arr[i];
        while(in.size() && (*in.begin()).l <= a.r){
            seg b = *in.begin();
           // cout << "ALIO" << endl;
            int rmin = min(b.r, a.r);
            int lmax = max(b.l, a.l);
            vals[a.time - b.time - 1] += rmin - lmax + 1;
            in.erase(b);
            if(b.r > a.r){
                seg c = {a.r+1, b.r, b.time};
                in.insert(c);
            }
        }
        in.insert(a);
    }
    vector<pair<int, int>> pref;
    for(auto[l, r] : vals){
        pref.push_back({l, r});
        //cout << l <<" " << r << endl;
    }
    pref.push_back({(int)1e16, 0ll});
    for(int i = (int)pref.size()-2; i > -1; i --){
        pref[i].second += pref[i+1].second;
    }
    for(auto[l, r] : pref){
       // cout << "P   " << l << " " << r << endl;
    }
    for(int i = 0; i < Q; i ++){
        int q;
        cin >> q;
        cout << (*lower_bound(pref.begin(), pref.end(), make_pair(q, 0ll))).second << " ";
    }
    cout << endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:54:13: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   54 |     for(auto[l, r] : pref){
      |             ^~~~~~

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