QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #136767 | #238. Distinct Values | freshmen# | 100 ✓ | 215ms | 5412kb | C++14 | 1.3kb | 2023-08-09 11:07:14 | 2023-08-09 11:07:20 |
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;
if(l<=lsr){
for(int j=lsl;j<l;++j){
chk[prt[j]]--;
if(chk[prt[j]]==0) q.push(prt[j]);
}
for(int j=lsr+1;j<=r;++j){
prt[j]=q.top();q.pop();
chk[prt[j]]++;
}
}
else{
for(int j=lsl;j<=lsr;++j){
chk[prt[j]]--;
if(chk[prt[j]]==0) q.push(prt[j]);
}
for(int j=l;j<=r;++j){
prt[j]=q.top();q.pop();
chk[prt[j]]++;
}
}
lsl=l;lsr=r;
}
for(int i=1;i<=n;++i) if(prt[i]==0) 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;
}
/*
5
10 5
6 9
1 6
2 3
8 8
3 7
10 3
1 2
6 9
2 6
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 215ms
memory: 5412kb
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 ...
result:
ok 11116 lines