QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#56715 | #238. Distinct Values | mango8023 | AC ✓ | 362ms | 9264kb | C++ | 1016b | 2022-10-21 09:17:56 | 2022-10-21 09:17:57 |
Judging History
answer
#include <cstdio>
#include <iostream>
#include <set>
using namespace std;
const int N = 1E5+5;
int n, k, pre[N], ans[N];
int main(){
int t = 0;
scanf("%d", &t);
while(t--){
scanf("%d%d", &k, &n);
for(int i=1;i<=k;i++) pre[i] = i;
for(int i=0;i<n;i++){
int l, r;
scanf("%d%d", &l, &r);
pre[r] = min(pre[r], l);
}
for(int i=k-1;i>=0;i--){
pre[i] = min(pre[i], pre[i+1]);
}
int num = 1;
set<int> val;
for(int i=1;i<=k;i++) val.insert(i);
for(int i=1;i<=k;i++){ // O(k*log(k) + k + k*(1+log(k)))
while(num < pre[i]){
val.insert(ans[num]); // O(k log k)
num++; // O(k)
}
ans[i] = *val.begin(); // O(1)
val.erase(ans[i]); // O(log k)
}
for(int i=1;i<=k;i++){
printf("%d%c", ans[i], i==k?'\n':' ');
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 362ms
memory: 9264kb
input:
11116 10 2 5 5 5 6 10 1 7 10 10 1 2 6 10 1 2 5 10 1 6 7 10 2 8 9 7 10 10 2 1 4 6 10 10 4 8 8 10 10 3 6 1 5 10 3 8 8 10 10 8 10 10 4 6 10 1 5 2 6 1 2 10 3 4 4 4 8 4 8 10 4 1 5 1 2 5 5 2 4 10 4 2 5 9 10 6 7 2 4 10 1 5 6 10 4 10 10 8 10 2 5 10 10 10 1 1 2 10 4 7 8 5 6 7 9 10 10 10 4 3 7 6 6 8 10 3 4 10...
output:
1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 3 4 1 1 2 3 4 5 1 1 1 1 1 1 2 3 4 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 3 4 1 2 3 4 1 1 2 3 4 5 1 2 3 4 5 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 1 2 3 4 5 1 2 3 4 5 1 1 1 1 2 3 4 5 1 1 1 2 3 4 5 1 1 1 1 1 1 1 2 3 4 1 2 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 2 3 4 1 1 1 2 3 ...
result:
ok 11116 lines