QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#56715#238. Distinct Valuesmango8023AC ✓362ms9264kbC++1016b2022-10-21 09:17:562022-10-21 09:17:57

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-21 09:17:57]
  • 评测
  • 测评结果:AC
  • 用时:362ms
  • 内存:9264kb
  • [2022-10-21 09:17:56]
  • 提交

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