제출 #1121431

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121431		clams1606	Inspections (NOI23_inspections)	C++14	29 / 100	103 ms	17136 KiB

Main

#include <bits/stdc++.h>

#define _files
#define _multitest
#define _Debug

using namespace std;

void just_do_it();

int main() {
    #define task ""
    #ifdef _files_
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    #endif
    #ifdef _Debug
        ios_base::sync_with_stdio(0);
    #endif
    cin.tie(0);
    just_do_it();
    return 0;
}

#define __builtin_popcount __builtin_popcountll
#define BIT(x, i) (((x)>> (i))& (1LL))
#define MASK(x) (1LL<< (x))
#define MOD 1000000007
#define ll long long

const int maxm= (int)1e6, maxn= (int)1e5, maxb= (int)1e3, maxsz= (int)2e5, maxrsz= (int)4e6;

ll INF= (ll)1e18;

int n, m, q, l[maxsz+ 2], r[maxsz+ 2], pre[maxsz+ 2], ans[maxsz+ 2], sz, a[maxrsz+ 2], cnt[maxrsz+ 2], ntime;
pair<ll, int> s[maxsz+ 2];

void input(){
    cin>> n>> m>> q;
    for(int i= 1; i<= m; i++){
        cin>> l[i]>> r[i];
    }
    for(int i= 1; i<= q; i++){
        cin>> s[i].first;
        s[i].second= i;
    }
}

void prepare(){

}

void solve(){
    sort(s+ 1, s+ q+ 1, greater< pair<ll, int> >());
    ntime= 0;
    for(int j= 1; j<= m; j++){
        for(int i= l[j]; i<= r[j]; i++){
            if(pre[i]== 0){
                pre[i]= ++ntime;
            }
            else{
                cnt[ntime- pre[i]]++;
                pre[i]= ++ntime;
            }
        }
    }
    sz= 0;
    for(int i= maxrsz; i>= 0; i--){
        while(cnt[i]){
            a[++sz]= i;
            cnt[i]--;
        }
    }
    int j= 0;
    for(int iq= 1; iq<= q; iq++){
        while((j< sz)&& (a[j+ 1]>= s[iq].first)){
            j++;
        }
        ans[s[iq].second]= j;
    }
    for(int i= 1; i<= q; i++){
        cout<< ans[i]<< ' ';
    }
}

void printans(){

}

void reset(){

}

void test(){
    input();
    prepare();
    solve();
    printans();
    reset();
}

void just_do_it() {
    int nTest= 1;
    #ifdef _multitest_
        cin>>nTest;
    #endif
    for (int it= 1; it <= nTest; it++) {
        test();
    }
}

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