Submission #1114383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114383		Thunnus	Žarulje (COI15_zarulje)	C++17	100 / 100	500 ms	436520 KiB

zarulje

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 5;
int fact[MAXN], ifact[MAXN];

inline int binpow(int a, int b){
    int ret = 1;
    while(b){
        if(b & 1){
            ret = (ret * a) % MOD;
        }
        a = (a * a) % MOD;
        b >>= 1;
    }
    return ret;
}

inline int comb(int a, int b){
    int ret = (((fact[a] * ifact[b]) % MOD) * ifact[a - b]) % MOD;
    return ret;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    fact[0] = 1;
    for(int i = 1; i < MAXN; i++){
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    ifact[MAXN - 1] = binpow(fact[MAXN - 1], MOD - 2);
    for(int i = MAXN - 2; i >= 0; i--){
        ifact[i] = (ifact[i + 1] * (i + 1)) % MOD;
    }
    int n, k;
    cin >> n >> k;
    vi a(n + 1), b(k);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int &i : b){
        cin >> i;
    }

    vector<stack<pii>> to_le(n + 1), to_ri(n + 1);
    for(int i = 2; i <= n; i++){
        to_le[i] = to_le[i - 1];
        while(!to_le[i].empty() && a[i - 1] < to_le[i].top().fi){
            to_le[i].pop();
        }
        int cnt = 1;
        while(!to_le[i].empty() && a[i - 1] == to_le[i].top().fi){
            cnt += to_le[i].top().se;
            to_le[i].pop();
        }
        to_le[i].emplace(a[i - 1], cnt);
    }

    for(int i = n - 1; i >= 1; i--){
        to_ri[i] = to_ri[i + 1];
        while(!to_ri[i].empty() && a[i + 1] < to_ri[i].top().fi){
            to_ri[i].pop();
        }
        int cnt = 1;
        while(!to_ri[i].empty() && a[i + 1] == to_ri[i].top().fi){
            cnt += to_ri[i].top().se;
            to_ri[i].pop();
        }
        to_ri[i].emplace(a[i + 1], cnt);
    }

    vi ans(n + 1);
    for(int i = 0; i < k; i++){
        if(!ans[b[i]]){
            int res = 1;
            while(!to_le[b[i]].empty() && !to_ri[b[i]].empty()){
                if(to_le[b[i]].top().fi > to_ri[b[i]].top().fi){
                    to_le[b[i]].pop();
                }
                else if(to_ri[b[i]].top().fi > to_le[b[i]].top().fi){
                    to_ri[b[i]].pop();
                }
                else{
                    int cntl = to_le[b[i]].top().se, cntr = to_ri[b[i]].top().se;
                    res = (res * comb(cntl + cntr, cntr)) % MOD;
                    to_le[b[i]].pop(), to_ri[b[i]].pop();
                }
            }
            ans[b[i]] = res;
        }
        cout << ans[b[i]] << "\n";
    }
    return 0;
}

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