oj.uz

Submission #803053

# Submission time Handle Problem Language Result Execution time Memory
803053 2023-08-02T20:29:50 Z Ahmed57 Žarulje (COI15_zarulje) C++17
100 / 100
 717 ms 30760 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 15948 KB Output is correct
2 Correct 220 ms 15912 KB Output is correct
3 Correct 214 ms 16024 KB Output is correct
4 Correct 216 ms 16088 KB Output is correct
5 Correct 213 ms 15976 KB Output is correct
6 Correct 222 ms 15976 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 21420 KB Output is correct
2 Correct 423 ms 26596 KB Output is correct
3 Correct 428 ms 26716 KB Output is correct
4 Correct 428 ms 26956 KB Output is correct
5 Correct 439 ms 27284 KB Output is correct
6 Correct 441 ms 28120 KB Output is correct
7 Correct 443 ms 29056 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 15948 KB Output is correct
2 Correct 220 ms 15912 KB Output is correct
3 Correct 214 ms 16024 KB Output is correct
4 Correct 216 ms 16088 KB Output is correct
5 Correct 213 ms 15976 KB Output is correct
6 Correct 222 ms 15976 KB Output is correct
7 Correct 322 ms 21420 KB Output is correct
8 Correct 423 ms 26596 KB Output is correct
9 Correct 428 ms 26716 KB Output is correct
10 Correct 428 ms 26956 KB Output is correct
11 Correct 439 ms 27284 KB Output is correct
12 Correct 441 ms 28120 KB Output is correct
13 Correct 443 ms 29056 KB Output is correct
14 Correct 232 ms 16592 KB Output is correct
15 Correct 449 ms 22904 KB Output is correct
16 Correct 675 ms 29744 KB Output is correct
17 Correct 563 ms 28304 KB Output is correct
18 Correct 699 ms 30208 KB Output is correct
19 Correct 563 ms 28396 KB Output is correct
20 Correct 699 ms 29780 KB Output is correct
21 Correct 717 ms 30760 KB Output is correct