QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#136731#242. RMQ Similar Sequencewhsyhyyh#100 ✓95ms27088kbC++141.2kb2023-08-09 10:42:092023-08-09 10:42:12

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-09 10:42:12]
  • Judged
  • Verdict: 100
  • Time: 95ms
  • Memory: 27088kb
  • [2023-08-09 10:42:09]
  • Submitted

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 1000010
#define LL long long
#define mod 1000000007
#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,n,a[N];
int st[N],top,L[N],R[N];
LL inv[N];
int main() {
	inv[0]=inv[1]=1;
	rep(i,2,N-10) inv[i]=mod-mod/i*inv[mod%i]%mod;
	
	T=rd();
	while(T--) {
		n=rd();
		rep(i,1,n) a[i]=rd();
		
		top=0;
		rep(i,1,n) {
			while(top&&a[i]>a[st[top]]) R[st[top]]=i-1,top--;
			st[++top]=i;
		}
		while(top) R[st[top]]=n,top--;
		
		drep(i,n,1) {
			while(top&&a[i]>=a[st[top]]) L[st[top]]=i+1,top--;
			st[++top]=i;
		}
		while(top) L[st[top]]=1,top--;
		
		LL ans=1;
		rep(i,1,n) ans=ans*inv[R[i]-L[i]+1]%mod/*,cerr<<"FUCK "<<i<<' '<<L[i]<<' '<<R[i]<<endl*/;
		printf("%lld\n",ans*n%mod*inv[2]%mod);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 95ms
memory: 27088kb

input:

11119
1
1
2
1 2
3
1 1 3
4
3 1 1 2
5
5 5 2 4 2
6
2 6 4 4 3 3
7
3 1 1 3 5 5 4
8
4 8 4 7 1 1 7 6
9
9 3 6 3 7 6 1 7 6
10
5 1 10 2 5 1 7 7 4 1
10
4 5 4 5 10 1 5 1 2 5
10
1 2 3 6 2 9 9 7 6 2
10
2 8 3 5 2 4 10 4 8 4
10
2 9 10 3 1 1 2 10 7 7
10
5 7 7 8 10 6 4 3 10 6
10
1 8 9 3 2 4 2 5 5 9
10
4 7 9 2 5 10 10...

output:

500000004
500000004
250000002
83333334
41666667
520833337
760416672
760416672
190104168
1984127
952083340
650694449
253472224
625744052
301388891
625744052
952083340
63368056
387723217
462574408
500992067
835648154
877232149
476041670
31684028
354456021
877232149
916832017
559076007
650694449
126736...

result:

ok 11119 lines