QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#136772#242. RMQ Similar Sequencenameless_story#100 ✓190ms105060kbC++20874b2023-08-09 11:11:092023-08-09 11:11:10

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 11:11:10]
  • Judged
  • Verdict: 100
  • Time: 190ms
  • Memory: 105060kb
  • [2023-08-09 11:11:09]
  • Submitted

answer

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL mod=1e9+7;
LL inv(LL x){return x==1?1:(mod-mod/x)*inv(mod%x)%mod;}
void solve(){
    LL n; cin>>n;
    vector<LL> a(n+1),sz(n+1),ls(n+1),rs(n+1);
    stack<LL> stk;
    stk.push(0); a[0]=n;
    for (LL i=1;i<=n;++i){
        cin>>a[i];
        for (;!stk.empty()&&a[stk.top()]<a[i];stk.pop()){
            ls[i]=stk.top();
        }
        rs[stk.top()]=i;
        stk.push(i);
    }
    function<LL(LL)> dfs=[&](LL x){
        if (!x) return 1LL;
        LL lc=dfs(ls[x]);
        LL rc=dfs(rs[x]);
        sz[x]=sz[ls[x]]+sz[rs[x]]+1;
        return lc*rc%mod*sz[x]%mod;
    };
    LL ans=dfs(rs[0]);
    ans=inv(ans)*inv(2)%mod*n%mod;
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    LL T; cin>>T;
    while (T--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 190ms
memory: 105060kb

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