Submission #954491

#	Time	Username	Problem	Language	Result	Execution time	Memory
954491		vjudge1	Žarulje (COI15_zarulje)	C++17	60 / 100	1022 ms	7252 KiB

zarulje

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=1e9+7,N=1<<18;
int H[N],fac[N],inv[N];
int pw(int x,int k){
    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;
}
signed main(){
    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],M-2);
    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];
    while(k--){
        int x;
        cin>>x;
        stack<int>l,r;
        l.push(0),r.push(0);
        for(int i=1;i<x;l.push(H[i++]))
            while(l.top()>H[i])
                l.pop();
        for(int i=n;i>x;r.push(H[i--]))
            while(r.top()>H[i])
                r.pop();
        map<int,int> mp1,mp2;
        int res=1;
        while(l.size())
            mp1[l.top()]++,l.pop();
        while(r.size())
            mp2[r.top()]++,r.pop();
        mp1.erase(0);
        for(auto[i,j]:mp1)
            res=res*C(j,mp2[i])%M;
        cout<<res<<'\n';
    }
}

• Subtask 1: 22 / 22
• Subtask 2: 38 / 38
• Subtask 3: 0 / 40