Submission #167296

#	Time	Username	Problem	Language	Result	Execution time	Memory
167296		farmerboy	Žarulje (COI15_zarulje)	C++14	100 / 100	206 ms	11932 KiB

zarulje

/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/
 
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x
 
using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<int, II> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;
 
const ll MODBASE = 1000000007LL;
const int MAXN = 200010;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

int n, q, a[MAXN], smallR[MAXN], lCnt[MAXN], rCnt[MAXN], f[MAXN];
ll res[MAXN], fac[MAXN], inv[MAXN];
stack<int> s;
vector<II> lChanges, rChanges;
set<int> changed;

ll C(int n, int k) {
    return fac[n] * inv[n-k] % MODBASE * inv[k] % MODBASE;
}

ll invC(int n, int k) {
    return fac[n-k] * fac[k] % MODBASE * inv[n] % MODBASE;
}

ll binPowMod(ll a, ll b, ll m) {
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1LL) res = res * a % m;
        a = a * a % m;
        b >>= 1LL;
    }
    return res;
}

void solve() {
    a[0] = a[n+1] = 0;
    fac[0] = 1;
    inv[0] = binPowMod(fac[0], MODBASE-2, MODBASE);
    FOR(i,1,n) {
        fac[i] = fac[i-1] * i % MODBASE;
        inv[i] = binPowMod(fac[i], MODBASE-2, MODBASE);
    }
    s.push(0);
    FOR(i,1,n+1) {
        while (SZ(s) && a[i] <= a[s.top()]) {
            int h = s.top();
            smallR[h] = i;
            s.pop();
        }
        s.push(i);
    }
    while (SZ(s)) s.pop();

    // FOR(i,1,n) cout << smallR[i] << ' '; cout << endl;

    int p = 2;
    while (p <= n) {
        rCnt[a[p]]++;
        f[p] = 1;
        p = smallR[p];
    }

    res[1] = 1;
    res[n] = 1;
    s.push(0);
    ll kq = 1;
    FOR(i,2,n-1) {
        changed.clear();
        lChanges.clear();
        rChanges.clear();
        while (a[i-1] < a[s.top()]) {
            int h = s.top();
            lChanges.emplace_back(II(a[h], -1));
            changed.insert(a[h]);
            s.pop();
        }
        s.push(i-1);
        lChanges.emplace_back(II(a[i-1], 1));
        changed.insert(a[i-1]); 

        f[i] = 0;
        rChanges.emplace_back(II(a[i], -1));
        changed.insert(a[i]); 

        int p = i+1;
        while (p <= n) {
            if (f[p]) break;
            rChanges.emplace_back(II(a[p], 1));
            changed.insert(a[p]);
            f[p] = 1;
            p = smallR[p];
        }

        FORALL(it, changed) kq = kq * invC(lCnt[*it] + rCnt[*it], lCnt[*it]) % MODBASE;

        // cout << i << endl;
        // FOR(j,0,SZ(lChanges)-1) cout << lChanges[j].FI << ' ' << lChanges[j].SE << endl;
        // cout << "----" << endl;
        // FOR(j,0,SZ(rChanges)-1) cout << rChanges[j].FI << ' ' << rChanges[j].SE << endl;

        FOR(j,0,SZ(lChanges)-1) lCnt[lChanges[j].FI] += lChanges[j].SE;
        FOR(j,0,SZ(rChanges)-1) rCnt[rChanges[j].FI] += rChanges[j].SE;

        FORALL(it, changed) {
            kq = kq * C(lCnt[*it] + rCnt[*it], lCnt[*it]) % MODBASE;
            // cout << *it << ' ';
        }
        // cout << endl << endl;

        res[i] = kq;
    }

    // FOR(i,1,n) cout << res[i] << ' '; cout << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> q;
    FOR(i,1,n) cin >> a[i];

    solve();

    while (q--) {
        int x;
        cin >> x;
        cout << res[x] << "\n";
    }
    return 0;
}

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