oj.uz

Submission #167296

# Submission time Handle Problem Language Result Execution time Memory
167296 2019-12-07T08:33:59 Z farmerboy Žarulje (COI15_zarulje) C++14
100 / 100
 206 ms 11932 KB 
/*
    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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 4 ms 504 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 4376 KB Output is correct
2 Correct 155 ms 7864 KB Output is correct
3 Correct 133 ms 8032 KB Output is correct
4 Correct 140 ms 8168 KB Output is correct
5 Correct 136 ms 8432 KB Output is correct
6 Correct 141 ms 9336 KB Output is correct
7 Correct 150 ms 10212 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 70 ms 4376 KB Output is correct
8 Correct 155 ms 7864 KB Output is correct
9 Correct 133 ms 8032 KB Output is correct
10 Correct 140 ms 8168 KB Output is correct
11 Correct 136 ms 8432 KB Output is correct
12 Correct 141 ms 9336 KB Output is correct
13 Correct 150 ms 10212 KB Output is correct
14 Correct 10 ms 888 KB Output is correct
15 Correct 89 ms 5856 KB Output is correct
16 Correct 161 ms 11256 KB Output is correct
17 Correct 159 ms 9720 KB Output is correct
18 Correct 193 ms 11436 KB Output is correct
19 Correct 167 ms 9720 KB Output is correct
20 Correct 185 ms 11156 KB Output is correct
21 Correct 206 ms 11932 KB Output is correct