oj.uz

Submission #363715

# Submission time Handle Problem Language Result Execution time Memory
363715 2021-02-07T00:21:21 Z jainbot27 Žarulje (COI15_zarulje) C++17
100 / 100
 117 ms 24044 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

// modulo class
namespace modulo{
    int fact[mxN], invfact[mxN];
    int add(const int& x, const int& y){ int res = x; res += y; while(res >= MOD) res -= MOD; while(res < 0) res += MOD; return res; } 
    void ad(int &x, const int& y) {x = add(x, y);}
    int sub(const int& x, const int& y){ int res = x; res -= y; while(res >= MOD) res -= MOD; while(res < 0) res += MOD; return res; } 
    void sb(int &x, const int& y) {x = sub(x, y);}
    int mul(const int& x, const int& y){ return (1LL*x*y) % MOD; } 
    void ml(int &x, const int& y) {x = mul(x, y);}
    int binpow(int x, int y){ int z = 1; while(y > 0) { if(y % 2 == 1) z = mul(z, x); x = mul(x, x); y /= 2; } return z; }
    int inv(const int& x){ return binpow(x, MOD - 2); }
    int divide(const int& x, const int& y){ return mul(x, inv(y)); }
    void precalc(){ 
        fact[0] = 1; 
        for(int i = 1; i < mxN; i++) fact[i] = mul(i, fact[i - 1]); 
        invfact[mxN-1] = inv(fact[mxN-1]);
        for(int i = mxN - 2; i >= 0; i--) invfact[i] = mul(invfact[i+1], i+1);
    }
    int choose(const int& n, const int& k){ if(k > n) return 0; return mul(fact[n], mul(invfact[n-k], invfact[k])); }
    int invchoose(const int& n, const int& k){ if(k > n) return 0; return mul(invfact[n], mul(fact[n-k], fact[k])); }
};
using namespace modulo;

int n, k;
int a[mxN];
stack<int> stk;
vi l[mxN], r[mxN];
int lc[mxN], rc[mxN];
int ans[mxN];

void update(int pos, int val, int lx, int add){
    //cout << pos << ' ' << val << ' ' << lx << ' ' << add << 
    //' ' << lc[val] << ' ' << rc[val] << ' ' << invchoose(lc[val]+rc[val], lc[val]) << nl;
    ml(ans[pos], invchoose(lc[val]+rc[val], lc[val]));
    if(lx){
        if(add) lc[val]++;
        else lc[val]--;        
    }
    else{
        if(add) rc[val]++;
        else rc[val]--;
    }
    ml(ans[pos], choose(lc[val]+rc[val], lc[val]));
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    precalc();
    F0R(i, n) cin >> a[i];
    F0R(i, n){
        while(siz(stk)&&stk.top()>a[i]){
            l[i].pb(stk.top());
            stk.pop();
        }
        stk.push(a[i]);
    }
    stk=stack<int>();
    R0F(i, n){
        while(siz(stk)&&stk.top()>a[i]){
            r[i].pb(stk.top());
            rc[stk.top()]--;
            stk.pop();
        }
        stk.push(a[i]);
        rc[a[i]]++;
    }
    F0R(i, n){
        ans[i] = (i==0?1:ans[i-1]);
        if(i){
            update(i, a[i-1], 1, 1);
            trav(v, l[i-1]) update(i, v, 1, 0);
        }
        update(i, a[i], 0, 0);
        trav(v, r[i]) update(i, v, 0, 1);
    }
    while(k--){
        int q; cin >> q;
        cout << ans[q-1] << nl;
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11372 KB Output is correct
2 Correct 11 ms 11372 KB Output is correct
3 Correct 11 ms 11392 KB Output is correct
4 Correct 13 ms 11500 KB Output is correct
5 Correct 11 ms 11372 KB Output is correct
6 Correct 13 ms 11472 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15724 KB Output is correct
2 Correct 65 ms 19308 KB Output is correct
3 Correct 70 ms 19968 KB Output is correct
4 Correct 71 ms 20076 KB Output is correct
5 Correct 72 ms 20460 KB Output is correct
6 Correct 77 ms 21376 KB Output is correct
7 Correct 81 ms 22144 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11372 KB Output is correct
2 Correct 11 ms 11372 KB Output is correct
3 Correct 11 ms 11392 KB Output is correct
4 Correct 13 ms 11500 KB Output is correct
5 Correct 11 ms 11372 KB Output is correct
6 Correct 13 ms 11472 KB Output is correct
7 Correct 40 ms 15724 KB Output is correct
8 Correct 65 ms 19308 KB Output is correct
9 Correct 70 ms 19968 KB Output is correct
10 Correct 71 ms 20076 KB Output is correct
11 Correct 72 ms 20460 KB Output is correct
12 Correct 77 ms 21376 KB Output is correct
13 Correct 81 ms 22144 KB Output is correct
14 Correct 17 ms 12012 KB Output is correct
15 Correct 60 ms 17280 KB Output is correct
16 Correct 109 ms 22508 KB Output is correct
17 Correct 92 ms 21692 KB Output is correct
18 Correct 114 ms 23404 KB Output is correct
19 Correct 97 ms 21584 KB Output is correct
20 Correct 114 ms 23020 KB Output is correct
21 Correct 117 ms 24044 KB Output is correct