제출 #1146276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146276		monostack	Inspections (NOI23_inspections)	C++20	29 / 100	761 ms	1114112 KiB

Main

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

int32_t main(){
    int n,m,q; cin>>n>>m>>q;
    vector<pair<int,int>> in(m); 
    vector<int> queries(q);
    int sz = 0;
    for(int i = 0; i < m; i++){
        int a,b; cin>>a>>b;
        sz += b-a+1;
        in[i] = {a-1,b-1};
    }
    for(int i = 0; i < q; i++){
        int s; cin>>s;
        queries[i] = s;
    }
    vector<int> sbs(sz,0);
    vector<int> hai(n,-1);
    int p = -1;
    for(int i = 0; i < m; i++){
        for(int cur = in[i].first; cur <= in[i].second; cur++){
            ++p;
            if(hai[cur] == -1){
                hai[cur] = p;
            }else{
                sbs[p - hai[cur] - 1]++;
                hai[cur] = p;
            }
        }
    }
    vector<int> suf_sbs(sz+1,0);
    for(int i = sz; i > 0; i--) suf_sbs[i-1] = suf_sbs[i] + sbs[i-1];
    for(int i = 0; i < q; i++){
        if(queries[i] >= suf_sbs.size()){
            cout<<0<<'\n';
            continue;
        }
        cout<<suf_sbs[queries[i]]<<'\n';
    } 
}

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