제출 #1146297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146297		monostack	Inspections (NOI23_inspections)	C++20	29 / 100	765 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);
    bool c3 = true;
    int sz = 0;
    vector<int> szi(m);
    for(int i = 0; i < m; i++){
        int a,b; cin>>a>>b;
        sz += b-a+1;
        in[i] = {a-1,b-1};
        szi[i] = b-a+1;
        if(a != 1) c3 = false;
    }
    for(int i = 0; i < q; i++){
        int s; cin>>s;
        queries[i] = s;
    }
    if(c3 && n > 2000){
        vector<int> vsz(n,0);
        for(int i = 0; i < m-1; i++) vsz[szi[i]-1] += min(szi[i], szi[i+1]);
        vector<int> sf(n+1,0);
        for(int i = n; i > 0; i--) sf[i-1] = sf[i] + vsz[i-1];
        for(int i = 0; i < q; i++){
            if(queries[i] <= n) cout<<sf[queries[i]]<<'\n'; 
            else cout<<0<<'\n';
        }    
    }else{
        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