QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #243369 | #964. Excluded Min | linweitong | WA | 8ms | 39068kb | C++14 | 4.7kb | 2023-11-08 07:23:12 | 2023-11-08 07:23:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=500005,inf=1e9;
int n,q,a[N],bz[N],ans[N],mxx,maxx[N],mxid[N];
struct node{int l,r,id;}b[N];
vector<int>v[N];
bool cmp(node x,node y){return x.l==y.l?(x.r>y.r):(x.l<y.l);}
struct BIT{
int tr[N];
void add(int x,int v){for (int i=x;i<=n;i+=(i&(-i)))tr[i]+=v;}
int query(int x){int s=0;for (int i=x;i;i-=(i&(-i)))s+=tr[i];return s;}
int qry(int l,int r){return query(r)-query(l-1);}
}t1;
struct sgt1{
int mx[N<<2],id[N<<2],tag[N<<2];
void pushup(int x){
if (mx[x<<1]>mx[x<<1|1]){
mx[x]=mx[x<<1];
id[x]=id[x<<1];
}
else{
mx[x]=mx[x<<1|1];
id[x]=id[x<<1|1];
}
}
void pushdown(int x){
if (tag[x]!=0){
mx[x<<1]+=tag[x];
mx[x<<1|1]+=tag[x];
tag[x<<1]+=tag[x];
tag[x<<1|1]+=tag[x];
tag[x]=0;
}
}
void build(int l,int r,int x){
if (l==r){
if (bz[l])mx[x]=t1.qry(b[l].l,b[l].r);
else mx[x]=-inf;
id[x]=l;
return;
}
int mid=(l+r)>>1;
build(l,mid,x<<1),build(mid+1,r,x<<1|1);
pushup(x);
}
void modify1(int x,int l,int r,int L,int R,int v){
if (r<L||l>R)return;
if (L<=l&&r<=R){mx[x]+=v,tag[x]+=v;return;}
pushdown(x);
int mid=(l+r)>>1;
modify1(x<<1,l,mid,L,R,v),modify1(x<<1|1,mid+1,r,L,R,v);
pushup(x);
}
void modify2(int x,int l,int r,int k,bool ck){
if (l==r){mx[x]=ck?(-inf):(t1.qry(b[l].l,b[l].r));return;}
pushdown(x);
int mid=(l+r)>>1;
if (k<=mid)modify2(x<<1,l,mid,k,ck);
else modify2(x<<1|1,mid+1,r,k,ck);
pushup(x);
}
}t2;
struct Triple{
int L,R,id;
};
struct Node{
int x,id;
friend bool operator<(Node x,Node y){
return x.x<y.x;
}
};
set<Node>e[N];
set<Node>s1,s2;
struct sgt2{
int mx[N<<2],id[N<<2],idd[N<<2];
void pushup(int x){
if (mx[x<<1]>mx[x<<1|1]){
mx[x]=mx[x<<1];
id[x]=id[x<<1];
idd[x]=idd[x<<1];
}
else if (mx[x<<1]<mx[x<<1|1]){
mx[x]=mx[x<<1|1];
id[x]=id[x<<1|1];
idd[x]=idd[x<<1|1];
}
else{
if (id[x<<1]<id[x<<1|1]){
mx[x]=mx[x<<1];
id[x]=id[x<<1];
idd[x]=idd[x<<1];
}
else{
mx[x]=mx[x<<1|1];
id[x]=id[x<<1|1];
idd[x]=idd[x<<1|1];
}
}
}
void build(int l,int r,int x){
if (l==r){mx[x]=maxx[l],id[x]=l,idd[x]=mxid[l];return;}
int mid=(l+r)>>1;
build(l,mid,x<<1),build(mid+1,r,x<<1|1);
pushup(x);
}
Triple query(int x,int l,int r,int L,int R){
if (r<L||l>R)return (Triple){0,0,0};
if (L<=l&&r<=R)return (Triple){id[x],mx[x],idd[x]};
int mid=(l+r)>>1;
Triple s1=query(x<<1,l,mid,L,R),s2=query(x<<1|1,mid+1,r,L,R);
if (s1.R!=s2.R)return s1.R>s2.R?s1:s2;
return s1;
}
void modify(int x,int l,int r,int k){
if (l==r){
if (e[l].empty())mx[x]=0,id[x]=0,idd[x]=0;
else{
Node u=(*e[l].begin());
mx[x]=-u.x;
id[x]=l;
idd[x]=u.id;
}
return;
}
int mid=(l+r)>>1;
if (k<=mid)modify(x<<1,l,mid,k);
else modify(x<<1|1,mid+1,r,k);
pushup(x);
}
}t3;
int main(){
scanf("%d%d",&n,&q);
for (int i=1;i<=n;++i){
scanf("%d",&a[i]);
v[a[i]].push_back(i);
t1.add(i,1);
mxx=max(mxx,a[i]);
}
for (int i=1;i<=q;++i)scanf("%d%d",&b[i].l,&b[i].r),b[i].id=i;
sort(b+1,b+q+1,cmp);
for (int i=1;i<=q;++i){
e[b[i].l].insert((Node){-b[i].r,i});
}
for (int i=1;i<=n;++i){
if (!e[i].empty()){
maxx[i]=-(*e[i].begin()).x;
mxid[i]=(*e[i].begin()).id;
}
}
t3.build(1,n,1);
int o=0;
for (int i=1;i<=q;++i){
if (b[i].r>o){
o=b[i].r;
bz[i]=1;
s1.insert((Node){-b[i].l,i});
s2.insert((Node){b[i].r,i});
}
}
t2.build(1,q,1);
mxx=max(mxx,n);
for (int i=mxx+1;i>=0;--i){
for (int j:v[i]){
t1.add(j,-1);
int L,R;
if (s1.lower_bound((Node){-j,0})!=s1.end())R=(*s1.lower_bound((Node){-j,0})).id;
else R=-1;
if (s2.lower_bound((Node){j,0})!=s2.end())L=(*s2.lower_bound((Node){j,0})).id;
else L=-1;
if (L!=-1&&R!=-1)t2.modify1(1,1,q,L,R,-1);
}
while (t2.mx[1]>=i){
int x=t2.id[1];
ans[b[x].id]=i;
t2.modify2(1,1,q,x,1);
e[b[x].l].erase((Node){-b[x].r,x});
t3.modify(1,1,n,b[x].l);
bz[x]=2;
int las,nex;
if (s1.lower_bound((Node){1-b[x].l,0})!=s1.end())las=(*s1.lower_bound((Node){1-b[x].l,0})).id;
else las=0;
if (s2.lower_bound((Node){b[x].r+1,0})!=s2.end())nex=(*s2.lower_bound((Node){b[x].r+1,0})).id;
else nex=0;
s1.erase(s1.lower_bound((Node){-b[x].l,0}));
s2.erase(s2.lower_bound((Node){b[x].r,0}));
int L=b[x].l,R=(nex?(b[nex].l-1):n),lim=(las?(b[las].r+1):1);
while (L<=R){
Triple u=t3.query(1,1,n,L,R);
if (u.id==0||u.R<lim)break;
bz[u.id]=1;
s1.insert((Node){-u.L,u.id});
s2.insert((Node){u.R,u.id});
t2.modify2(1,1,q,u.id,0);
R=u.L-1;
}
}
}
for (int i=1;i<=q;++i)printf("%d\n",ans[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 38828kb
input:
3 3 0 0 2 1 3 2 3 3 3
output:
3 1 0
result:
ok 3 number(s): "3 1 0"
Test #2:
score: 0
Accepted
time: 0ms
memory: 38888kb
input:
3 2 1 2 2 1 2 1 3
output:
0 3
result:
ok 2 number(s): "0 3"
Test #3:
score: 0
Accepted
time: 4ms
memory: 38832kb
input:
10 10 3 0 3 3 9 7 9 6 0 7 3 3 9 9 4 6 1 9 3 4 2 4 7 10 3 7 5 7 2 7
output:
0 1 0 5 0 1 1 0 0 1
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 38832kb
input:
10 10 3 0 0 0 5 1 1 1 2 1 1 2 8 8 5 7 1 7 2 2 1 5 5 6 4 6 3 10 6 8
output:
1 0 2 7 1 4 0 2 8 3
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 8ms
memory: 38872kb
input:
100 100 15 82 7 39 63 55 64 99 71 63 32 99 67 94 3 43 15 75 45 55 53 4 35 36 15 40 82 20 62 43 6 83 27 95 27 45 98 44 35 98 39 7 17 32 76 7 40 16 40 63 13 8 22 27 11 12 61 14 19 45 100 97 90 88 22 59 25 63 4 25 65 16 22 92 84 44 99 66 89 26 93 97 35 97 92 1 32 40 97 97 78 43 7 12 23 53 61 74 33 90 1...
output:
68 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 48 0 0 0 0 0 0 0 0 0 0 0 0 0 28 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 100 numbers
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 39068kb
input:
100 100 17 86 33 8 11 27 8 11 13 9 3 43 11 23 26 42 44 12 44 12 15 0 75 51 72 5 49 2 40 57 24 47 39 42 4 5 6 52 3 2 42 19 62 33 24 22 16 69 4 33 44 70 29 11 2 2 58 9 6 10 25 10 33 26 17 3 14 0 48 7 48 51 0 39 54 37 14 9 3 85 18 4 25 9 2 0 39 8 17 13 25 45 10 39 12 18 9 5 66 6 13 89 10 90 42 67 43 52...
output:
76 80 0 0 18 1 18 1 5 5 1 1 22 11 0 15 0 59 5 56 1 80 0 1 1 21 0 61 22 0 0 3 8 15 40 1 8 81 71 20 2 0 60 0 60 31 0 59 0 0 0 28 0 21 1 7 5 0 31 0 76 28 0 0 27 1 23 0 1 27 1 0 0 1 0 5 63 52 2 43 73 1 86 0 61 0 27 2 30 5 31 1 0 14 59 27 1 1 67 63
result:
wrong answer 30th numbers differ - expected: '11', found: '0'