oj.uz

Submission #725025

# Submission time Handle Problem Language Result Execution time Memory
725025 2023-04-16T13:10:50 Z grogu Žarulje (COI15_zarulje) C++14
100 / 100
 929 ms 26084 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
using namespace std;

#define mod 1000000007
#define maxn 200005
ll fact[maxn];
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
ll po(ll x,ll y){
    if(y==0) return 1LL;
    ll ans = po(x,y/2);
    ans = mul(ans,ans);
    if(y&1) ans = mul(ans,x);
    return ans;
}
ll inv(ll x){return po(x,mod-2);}
ll ch(ll n,ll k){
    if(k>n) return 0;
    ll ans = fact[n];
    ans = mul(ans,inv(fact[k]));
    ans = mul(ans,inv(fact[n-k]));
    return ans;
}
ll n,k;
ll a[maxn];
ll ask[maxn];
ll rez[maxn];
ll cntl[maxn],cntr[maxn];
vector<pll> v[maxn];
void tc(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    fact[0] = 1;
    for(ll i = 1;i<maxn;i++) fact[i] = mul(fact[i-1],i);
    cin >> n >> k;
    for(ll i = 1;i<=n;i++) cin >> a[i];
    ll ans = 1;
    stack<ll> st;
    for(ll i = n;i>=1;i--){
        while(st.size()&&st.top()>a[i]){
            cntr[st.top()]--;
            v[i].pb({st.top(),1});
            st.pop();
        }
        cntr[a[i]]++;
        v[i].pb({a[i],-1});
        st.push(a[i]);
    }
    while(st.size()) st.pop();
    for(ll i = 1;i<=n;i++){
        for(pll p : v[i]){
            ll x = p.fi;
            ll d = p.sc;
            ans = mul(ans,inv(ch(cntr[x]+cntl[x],cntl[x])));
            cntr[x]+=d;
            ans = mul(ans,ch(cntr[x]+cntl[x],cntl[x]));
        }
        rez[i] = ans;
        while(st.size()&&st.top()>a[i]){
            ll x = st.top();
            ans = mul(ans,inv(ch(cntr[x]+cntl[x],cntl[x])));
            cntl[x]--;
            ans = mul(ans,ch(cntr[x]+cntl[x],cntl[x]));
            st.pop();
        }
        ll x = a[i];
        ans = mul(ans,inv(ch(cntr[x]+cntl[x],cntl[x])));
        cntl[x]++;
        ans = mul(ans,ch(cntr[x]+cntl[x],cntl[x]));
        st.push(a[i]);
    }
    for(ll i = 1;i<=k;i++){
        ll x; cin >> x;
        cout<<rez[x]<<endl;
    }
}

int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	int t; t = 1;
	while(t--){
		tc();
	}
	return 0;
}
/**
5 2
3 5 1 4 3
3 5
**/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6612 KB Output is correct
2 Correct 9 ms 6596 KB Output is correct
3 Correct 15 ms 6760 KB Output is correct
4 Correct 17 ms 6772 KB Output is correct
5 Correct 13 ms 6768 KB Output is correct
6 Correct 14 ms 6740 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 13720 KB Output is correct
2 Correct 848 ms 20184 KB Output is correct
3 Correct 884 ms 20636 KB Output is correct
4 Correct 884 ms 20736 KB Output is correct
5 Correct 883 ms 21128 KB Output is correct
6 Correct 905 ms 22780 KB Output is correct
7 Correct 900 ms 24356 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6612 KB Output is correct
2 Correct 9 ms 6596 KB Output is correct
3 Correct 15 ms 6760 KB Output is correct
4 Correct 17 ms 6772 KB Output is correct
5 Correct 13 ms 6768 KB Output is correct
6 Correct 14 ms 6740 KB Output is correct
7 Correct 425 ms 13720 KB Output is correct
8 Correct 848 ms 20184 KB Output is correct
9 Correct 884 ms 20636 KB Output is correct
10 Correct 884 ms 20736 KB Output is correct
11 Correct 883 ms 21128 KB Output is correct
12 Correct 905 ms 22780 KB Output is correct
13 Correct 900 ms 24356 KB Output is correct
14 Correct 48 ms 7372 KB Output is correct
15 Correct 460 ms 15180 KB Output is correct
16 Correct 887 ms 23364 KB Output is correct
17 Correct 904 ms 22264 KB Output is correct
18 Correct 917 ms 23868 KB Output is correct
19 Correct 921 ms 22324 KB Output is correct
20 Correct 926 ms 24428 KB Output is correct
21 Correct 929 ms 26084 KB Output is correct