oj.uz

Submission #1110152

# Submission time Handle Problem Language Result Execution time Memory
1110152 2024-11-08T20:59:23 Z vjudge1 Žarulje (COI15_zarulje) C++17
100 / 100
 356 ms 191816 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Ls l.top()
#define Rs r.top()
#define calc(x) (fac[mp1[x]+mp2[x]]*inv[mp2[x]]%M*inv[mp1[x]]%M)
const int M=1e9+7,N=1<<18;
int H[N],fac[N],inv[N],res[N],mp1[N],mp2[N];
stack<int>bad[N],l,r;
int qp(int x,int k=M-2){
    if(!k) return 1;
    int y=qp(x,k/2);
    y=y*y%M;
    if(k&1)y=y*x%M;
    return y;
}
signed main(){
    l.push(0),r.push(0);
    cin.tie(0)->sync_with_stdio(0);
    fac[0]=1;
    for(int i=1;i<N;i++)
        fac[i]=fac[i-1]*i%M;
    inv[N-1]=qp(fac[N-1]);
    res[1]=1;
    for(int i=N;--i;)
        inv[i-1]=inv[i]*i%M;
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>H[i];
    for(int i=n;i>1;mp2[H[i]]++,r.push(H[i--]))
        while(Rs>H[i])
            bad[i].push(Rs),
            mp2[Rs]--,r.pop();
    for(int i=2;i<=n;i++) {
        res[i]=res[i-1];
        while(Ls>H[i-1])
            res[i]=res[i]*qp(calc(Ls))%M,
            mp1[Ls]--,res[i]=res[i]*calc(Ls)%M,l.pop();
        res[i]=res[i]*qp(calc(Rs))%M,mp2[Rs]--;
        res[i]=res[i]*calc(Rs)%M,r.pop();
        l.push(H[i-1]),res[i]=res[i]*qp(calc(Ls))%M;
        mp1[Ls]++,res[i]=res[i]*calc(Ls)%M;
        while(bad[i].size())
            r.push(bad[i].top()),res[i]=res[i]*qp(calc(Rs))%M,
            mp2[Rs]++,res[i]=res[i]*calc(Rs)%M,bad[i].pop();
    }
    while(k--){
        int x;
        cin>>x;
        cout<<res[x]<<'\n';
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 185160 KB Output is correct
2 Correct 140 ms 185160 KB Output is correct
3 Correct 131 ms 185168 KB Output is correct
4 Correct 131 ms 185340 KB Output is correct
5 Correct 125 ms 185160 KB Output is correct
6 Correct 128 ms 185328 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 186444 KB Output is correct
2 Correct 313 ms 187100 KB Output is correct
3 Correct 336 ms 187208 KB Output is correct
4 Correct 331 ms 187472 KB Output is correct
5 Correct 327 ms 187516 KB Output is correct
6 Correct 337 ms 189768 KB Output is correct
7 Correct 343 ms 189884 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 185160 KB Output is correct
2 Correct 140 ms 185160 KB Output is correct
3 Correct 131 ms 185168 KB Output is correct
4 Correct 131 ms 185340 KB Output is correct
5 Correct 125 ms 185160 KB Output is correct
6 Correct 128 ms 185328 KB Output is correct
7 Correct 234 ms 186444 KB Output is correct
8 Correct 313 ms 187100 KB Output is correct
9 Correct 336 ms 187208 KB Output is correct
10 Correct 331 ms 187472 KB Output is correct
11 Correct 327 ms 187516 KB Output is correct
12 Correct 337 ms 189768 KB Output is correct
13 Correct 343 ms 189884 KB Output is correct
14 Correct 141 ms 185428 KB Output is correct
15 Correct 244 ms 187976 KB Output is correct
16 Correct 344 ms 190332 KB Output is correct
17 Correct 350 ms 188744 KB Output is correct
18 Correct 352 ms 190536 KB Output is correct
19 Correct 331 ms 189000 KB Output is correct
20 Correct 356 ms 191560 KB Output is correct
21 Correct 344 ms 191816 KB Output is correct