QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#136740#238. Distinct Valuesfreshmen#0 196ms5540kbC++141.0kb2023-08-09 10:51:472023-08-09 10:51:48

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-09 10:51:48]
  • 评测
  • 测评结果:0
  • 用时:196ms
  • 内存:5540kb
  • [2023-08-09 10:51:47]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
int T,n,m,chk[200000],prt[200000];
struct node{
	int x,y;
}a[200000];
priority_queue<int,vector<int>,greater<int> >q;
int cmp(node a1,node b1){
	return (a1.x==b1.x)?(a1.y<b1.y):(a1.x<b1.x);
}
int main(){
	scanf("%d",&T);
	while(T--){
		int lsl=0,lsr=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;++i){
			scanf("%d%d",&a[i].x,&a[i].y);
		}
		for(int i=1;i<=n;++i) q.push(i);
		sort(a+1,a+m+1,cmp);
		for(int i=1;i<=m;++i){
			int l=a[i].x,r=a[i].y;
			if(r<=lsr) continue;
			for(int j=lsl;j<l;++j){
				chk[prt[j]]--;
				if(chk[prt[j]]==0) q.push(j);
			}
			for(int j=lsr+1;j<=r;++j){
				prt[j]=q.top();q.pop();
				chk[prt[j]]++;
			} 
			lsl=l;lsr=r;
		}
		if(lsr!=n) for(int i=lsr+1;i<=n;++i) prt[i]=1;
		for(int i=1;i<=n;++i) printf("%d ",prt[i]);
		puts("");
		while(!q.empty()) q.pop();
		for(int i=1;i<=n;++i) chk[i]=prt[i]=0;
	}
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 196ms
memory: 5540kb

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 2 3 4 5 6 1 1 1 1 
1 2 3 4 5 6 7 8 9 10 
1 2 3 4 5 6 1 1 1 1 
1 2 3 4 5 1 1 1 1 1 
1 2 3 4 5 6 7 1 1 1 
1 2 3 4 5 6 7 8 9 10 
1 2 3 4 1 2 3 4 5 6 
1 2 3 4 5 1 2 3 4 5 
1 2 3 4 5 6 7 8 9 10 
1 2 3 4 5 1 2 3 4 5 
1 2 3 4 5 6 7 8 1 1 
1 2 3 4 5 1 1 1 1 1 
1 2 3 4 5 2 3 4 5 6 
1 2 3 4 5 6 1 1 1 1 
1 2...

result:

wrong answer 1st lines differ - expected: '1 1 1 1 1 2 1 1 1 1', found: '1 2 3 4 5 6 1 1 1 1 '