Submission #803053

#	Time	Username	Problem	Language	Result	Execution time	Memory
803053		Ahmed57	Žarulje (COI15_zarulje)	C++17	100 / 100	717 ms	30760 KiB

zarulje

#include<bits/stdc++.h>
using namespace std;
//Fast
#define mod 1000000007

long long fact[1000001],inverse[1000001];
long long ans[200001];
long long fast(long long x,long long n)
{
    if (n == 0) {
        return 1;
    }
    long long pow = fast(x, n / 2)%mod;
    if (n & 1) {
        return ((((x%mod) * (pow%mod))%mod) * pow%mod)%mod;
    }
    return ((pow%mod) * (pow%mod))%mod;
}

long long solve(int a,int b){
    return((fact[a]*inverse[b])%mod*inverse[a-b])%mod;
}

pair<int,int> mp[200001];
long long res = 1;
void lol(int x,int i,int j){
    int p1 = mp[x].first;
    int p2 = mp[x].second;
    res *= fast(solve(p1+p2,p1),mod-2);res%=mod;
    if(i==1)p1+=j;
    else p2+=j;
    res *= solve(p1+p2,p1);res%=mod;
    mp[x].first = p1;
    mp[x].second = p2;
}
int main(){
    fact[0] = inverse[0] = fact[1] = inverse[1] = 1;
    for(int i = 2;i<=1e6;i++){
        fact[i]=fact[i-1]*i;
        fact[i]%=mod;
        inverse[i] = fast(fact[i],mod-2);
    }
    int n,m;
    cin>>n>>m;
    int arr[n+1];
    for(int i = 1;i<=n;i++){
        cin>>arr[i];
    }
    vector<int> adj[n+1];
    stack<int> st;
    for(int i = n;i>=1;i--){
        while(st.size()&&arr[i]<arr[st.top()]){
            adj[i].push_back(st.top());st.pop();
        }
        st.push(i);
    }
    while(st.size()){
        adj[1].push_back(st.top());st.pop();
    }
    for(int i = 1;i<=n;i++){
        for(auto j:adj[i]){
            lol(arr[j],1,1);
        }
        lol(arr[i],1,-1);
        ans[i] = res;
        while(st.size()&&arr[i]<arr[st.top()]){
            lol(arr[st.top()],2,-1);st.pop();
        }
        st.push(i);
        lol(arr[i],2,1);
    }
    for(int i = 1;i<=m;i++){
        int e;cin>>e;
        cout<<ans[e]<<endl;
    }
}

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