| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1121420 | clams1606 | Inspections (NOI23_inspections) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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)4e8;
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<int, 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<int, 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();
}
}