QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#32788#1096. Best Solution UnknownWu_RenWA 4ms7856kbC++171.1kb2022-05-23 20:45:302022-05-23 20:45:32

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-23 20:45:32]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:7856kb
  • [2022-05-23 20:45:30]
  • 提交

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'