QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #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;
}
Details
Tip: Click on the bar to expand more detailed information
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 '