oj.uz

Submission #954500

# Submission time Handle Problem Language Result Execution time Memory
954500 2024-03-28T04:50:55 Z boyliguanhan Žarulje (COI15_zarulje) C++17
100 / 100
 344 ms 203192 KB 
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#pragma GCC optimize(2)

const int M=1e9+7,N=1<<18;
#define L l.top()
#define R r.top()
int H[N],fac[N],inv[N],res[N];
stack<int>KILL[N],l,r;
gp_hash_table<int,int>mp1,mp2;
int pw(int x,int k=M-2){
    if(!k) return 1;
    int y=pw(x,k/2);
    y=y*y%M;
    if(k&1)y=y*x%M;
    return y;
}
int C(int a,int b){
    return fac[a+b]*inv[b]%M*inv[a]%M;
}
int get(int x){
    return C(mp1[x],mp2[x]);
}
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]=pw(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(R>H[i])
            KILL[i].push(R),mp2[R]--,r.pop();
    for(int i=2;i<=n;i++) {
        res[i]=res[i-1];
        while(L>H[i-1])
            res[i]=res[i]*pw(get(L))%M,mp1[L]--,res[i]=res[i]*get(L)%M,l.pop();
        res[i]=res[i]*pw(get(R))%M,mp2[R]--,res[i]=res[i]*get(R)%M,r.pop();
        l.push(H[i-1]),res[i]=res[i]*pw(get(L))%M,mp1[L]++,res[i]=res[i]*get(L)%M;
        while(KILL[i].size())
            r.push(KILL[i].top()),res[i]=res[i]*pw(get(R))%M,mp2[R]++,res[i]=res[i]*get(R)%M,KILL[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 86 ms 183108 KB Output is correct
2 Correct 87 ms 183116 KB Output is correct
3 Correct 89 ms 183124 KB Output is correct
4 Correct 87 ms 183252 KB Output is correct
5 Correct 90 ms 183376 KB Output is correct
6 Correct 90 ms 183316 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 184016 KB Output is correct
2 Correct 280 ms 184912 KB Output is correct
3 Correct 279 ms 184656 KB Output is correct
4 Correct 285 ms 184876 KB Output is correct
5 Correct 288 ms 186824 KB Output is correct
6 Correct 308 ms 203192 KB Output is correct
7 Correct 313 ms 203108 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 183108 KB Output is correct
2 Correct 87 ms 183116 KB Output is correct
3 Correct 89 ms 183124 KB Output is correct
4 Correct 87 ms 183252 KB Output is correct
5 Correct 90 ms 183376 KB Output is correct
6 Correct 90 ms 183316 KB Output is correct
7 Correct 183 ms 184016 KB Output is correct
8 Correct 280 ms 184912 KB Output is correct
9 Correct 279 ms 184656 KB Output is correct
10 Correct 285 ms 184876 KB Output is correct
11 Correct 288 ms 186824 KB Output is correct
12 Correct 308 ms 203192 KB Output is correct
13 Correct 313 ms 203108 KB Output is correct
14 Correct 99 ms 183124 KB Output is correct
15 Correct 202 ms 184916 KB Output is correct
16 Correct 310 ms 186760 KB Output is correct
17 Correct 293 ms 185668 KB Output is correct
18 Correct 303 ms 186600 KB Output is correct
19 Correct 306 ms 186956 KB Output is correct
20 Correct 321 ms 202932 KB Output is correct
21 Correct 344 ms 203040 KB Output is correct