QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#136740 | #238. Distinct Values | freshmen# | 0 | 196ms | 5540kb | C++14 | 1.0kb | 2023-08-09 10:51:47 | 2023-08-09 10:51:48 |
Judging History
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 '