QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#136646#238. Distinct Valueswhsyhyyh#0 174ms4860kbC++141.3kb2023-08-09 09:40:322023-08-09 09:40:35

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 09:40:35]
  • 评测
  • 测评结果:0
  • 用时:174ms
  • 内存:4860kb
  • [2023-08-09 09:40:32]
  • 提交

answer

#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define N 100010
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define drep(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
int rd() {
	int res=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
	return res*f;
}
int T;
int n,m;
struct info {
	int l,r;
}A[N];
bool cmp(info x,info y) {
	if(x.l^y.l)return x.l<y.l;
	return x.r<y.r;
}
priority_queue<int,vector<int>,greater<int> >Q;
int Ans[N];
int main() {
	T=rd();
	while(T--) {
		n=rd(),m=rd();
		for(int i=1; i<=m; ++i)A[i].l=rd(),A[i].r=rd();
		sort(A+1,A+m+1,cmp);
		for(int i=1; i<=n; ++i)Q.push(i); 
		for(int i=1; i<A[1].l; ++i)Ans[i]=1;
		int lx=A[1].l,rx=A[1].l;
		for(int i=1; i<=m; ++i) {
			while(A[i].l>lx)Q.push(Ans[lx]),lx++;
			while(rx<=A[i].r)Ans[rx]=Q.top(),Q.pop(),++rx;
		}
		while(rx<=n)Ans[rx]=1,++rx;
		while(!Q.empty())Q.pop();
		for(int i=1; i<n; ++i)printf("%d ",Ans[i]);
		printf("%d\n",Ans[n]); 
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 174ms
memory: 4860kb

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 2 2 2
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 2 2 3
...

result:

wrong answer 8th lines differ - expected: '1 2 3 4 5 1 1 1 1 1', found: '1 2 3 4 5 1 1 2 2 2'