QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #421062 | #238. Distinct Values | ship2077 | 100 ✓ | 155ms | 11108kb | C++14 | 1.5kb | 2024-05-25 10:54:03 | 2024-05-25 10:54:03 |
Judging History
answer
#include<bits/stdc++.h>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
constexpr int M=1e5+5,inf=0x3f3f3f3f;
int n,m,l,r,lg,tmp,st[20][M],tr[M<<2];
int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x;
}
void build(int l,int r,int x){
tr[x]=0;if (l==r) return;int mid=l+r>>1;
build(l,mid,ls(x));build(mid+1,r,rs(x));
}
void update(int p,int c,int l=1,int r=n,int x=1){
if (l==r) return tr[x]=c,void();int mid=l+r>>1;
p<=mid?update(p,c,l,mid,ls(x)):update(p,c,mid+1,r,rs(x));tr[x]=min(tr[ls(x)],tr[rs(x)]);
}
int query(int p,int l=1,int r=n,int x=1){
if (l==r) return l; int mid=l+r>>1;
return tr[ls(x)]<=p?query(p,l,mid,ls(x)):query(p,mid+1,r,rs(x));
}
void solve(){
n=read();m=read();
lg=31^__builtin_clz(n);
for (int j=1;j<=lg;j++)
for (int i=1;i+(1<<j)-1<=n;i++)
st[j][i]=inf;
auto upd=[&](auto l,auto r,auto p){
int k=31^__builtin_clz(r-l+1);
st[k][l]=min(st[k][l],p);
st[k][r+1-(1<<k)]=min(st[k][r+1-(1<<k)],p);
};
for (int i=1;i<=n;i++) st[0][i]=i;
for (int i=1;i<=m;i++) l=read(),r=read(),upd(l,r,l-1);
for (int j=lg;j;j--)
for (int i=1;i+(1<<j)-1<=n;i++)
st[j-1][i]=min(st[j-1][i],st[j][i]),
st[j-1][i+(1<<j-1)]=min(st[j-1][i+(1<<j-1)],st[j][i]);
build(1,n,1);
for (int i=1,tmp;i<=n;i++)
printf("%d%c",tmp=query(st[0][i])," \n"[i==n]),update(tmp,i);
}
int main(){int T=read(); while (T--) solve(); return 0;}
詳細信息
Test #1:
score: 100
Accepted
time: 155ms
memory: 11108kb
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 3 4 1 1 1 2 3 ...
result:
ok 11116 lines