QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#136646 | #238. Distinct Values | whsyhyyh# | 0 | 174ms | 4860kb | C++14 | 1.3kb | 2023-08-09 09:40:32 | 2023-08-09 09:40:35 |
Judging History
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'