QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#32788 | #1096. Best Solution Unknown | Wu_Ren | WA | 4ms | 7856kb | C++17 | 1.1kb | 2022-05-23 20:45:30 | 2022-05-23 20:45:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n,a[1000010],st[1000010],t,tr[4000010];
vector<int>ans;
void build(int l,int r,int t){
tr[t]=2e9;
if(l==r) return;
int mid=(l+r)>>1;
build(l,mid,t<<1),build(mid+1,r,t<<1|1);
}
void upd(int ql,int qr,int l,int r,int t,int c){
if(ql<=l&&r<=qr) return tr[t]=min(tr[t],c),void();
int mid=(l+r)>>1;
if(ql<=mid) upd(ql,qr,l,mid,t<<1,c);
if(mid<qr) upd(ql,qr,mid+1,r,t<<1|1,c);
}
int qry(int a,int l,int r,int t){
if(l==r) return tr[t];
int mid=(l+r)>>1;
return min(tr[t],a<=mid?qry(a,l,mid,t<<1):qry(a,mid+1,r,t<<1|1));
}
void sol(int ty){
st[t=1]=0;
for(int i=1;i<=n;i++){
for(;a[st[t]]<a[i];t--);
if(i==st[t]+1) continue;
if(ty) upd(n-i+2,n-st[t],1,n,1,a[i]-(i-st[t]-2));
else upd(st[t]+1,i-1,1,n,1,a[i]-(i-st[t]-2));
st[++t]=i;
}
}
int main(){
scanf("%d",&n);
a[0]=a[n+1]=2e9;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,n,1);
sol(0),reverse(a+1,a+n+1),sol(1);
for(int i=1;i<=n;i++) if(qry(i,1,n,1)>=a[i]) ans.push_back(i);
printf("%d\n",ans.size());
for(int i:ans) printf("%d ",i);puts("");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 7856kb
input:
3 3 2 2
output:
2 1 2
result:
wrong answer 1st numbers differ - expected: '3', found: '2'