제출 #1241777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241777		CodeLakVN	Žarulje (COI15_zarulje)	C++20	100 / 100	56 ms	18792 KiB

zarulje

#include <bits/stdc++.h>
using namespace std;

/*
- Observation: if there are 2 position i and i + 1 such that A_i < A_i+1 on the right side 
of initial postion X, then the light bulb i + 1 will always be turned off right after the light
bulb i, similar for the left side
==> So, with such light bulbs, their order to be turned off won't be changed, so we just need to
focus only on such positions A < B < C < X > D > E > F.
==> Then for each value of power, for example, we have cntL light bulbs on the left side have 
that value, and the similar cntR for the right side, then the answer is the multiplication
of C(cntL, cntR + cntL) because we have cntL + cntR spaces and we have to put cntL into those
spaces
*/

#define task "main"
#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)

const int MAX_N = (int)2e5 + 5;
const int MOD = (int)1e9 + 7;

int n, k;
int a[MAX_N], query[MAX_N];

int fact[MAX_N + 10], iFact[MAX_N + 10];

int binpow(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1) res = 1LL * res * x % MOD;
        x = 1LL * x * x % MOD;
        y >>= 1;
    }
    return res;
}

void init() {
    fact[0] = 1;
    FOR(i, 1, MAX_N - 1) fact[i] = 1LL * fact[i - 1] * i % MOD;
    iFact[MAX_N - 1] = binpow(fact[MAX_N - 1], MOD - 2);
    FOD(i, MAX_N - 2, 0) iFact[i] = 1LL * iFact[i + 1] * (i + 1) % MOD;
}

int C(int k, int n) {
    if (k > n) return 0;
    return 1LL * fact[n] * iFact[k] % MOD * iFact[n - k] % MOD; 
}

namespace sub12 {
    int cnt[MAX_N], cntL[MAX_N];
    
    int calc(int x) {
        int maxx = *max_element(a + 1, a + n + 1);
        FOR(i, 1, maxx) cnt[i] = cntL[i] = 0;

        vector<int> vitalPos;
        FOR(i, x + 1, n) {
            if (vitalPos.empty() || a[vitalPos.back()] >= a[i])
                vitalPos.push_back(i), cnt[a[i]]++;
        }
        
        vitalPos.clear();
        FOD(i, x - 1, 1) {
            if (vitalPos.empty() || a[vitalPos.back()] >= a[i])
                vitalPos.push_back(i), cnt[a[i]]++, cntL[a[i]]++;
        }

        int ans = 1;
        FOR(i, 1, maxx) ans = 1LL * ans * C(cntL[i], cnt[i]) % MOD;
        
        return ans; 
    }    
    
    void solve() {
        FOR(i, 1, k) cout << calc(query[i]) << "\n";
    }
}

namespace sub3 {
    int ans[MAX_N];
    int cntR[MAX_N], cntL[MAX_N];
    vector<ii> events[MAX_N];    
    int cur = 1;

    int mul(int x, int y) {
        return (1LL * x * y) % MOD;
    }

    void add(int &a, int b, int x) {
        cur = mul(cur, mul(fact[a], mul(fact[b], iFact[a + b]))); // remove the previous combination
        a += x;
        cur = mul(cur, mul(iFact[a], mul(iFact[b], fact[a + b]))); // add the new combination
    }

    void process() {
        vector<int> st;
        FOD(i, n, 1) {
            while (!st.empty() && a[st.back()] > a[i]) {
                cntR[a[st.back()]]--;
                events[i].push_back({a[st.back()], +1});
                st.pop_back();
            }
            events[i].push_back({a[i], -1});
            cntR[a[i]]++;
            st.push_back(i);
        }

        st.clear();
        FOR(i, 1, n) {
            for (ii &event : events[i])
                add(cntR[event.F], cntL[event.F], event.S);
            ans[i] = cur;

            while (!st.empty() && a[st.back()] > a[i]) {
                int val = a[st.back()];
                add(cntL[val], cntR[val], -1);
                st.pop_back();
            }
            add(cntL[a[i]], cntR[a[i]], +1);
            st.push_back(i);
        }
    }

    void solve() {
        process();
        FOR(i, 1, k) cout << ans[query[i]] << '\n';
    }
}

void solve() {
    cin >> n >> k;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, k) cin >> query[i];

    init();

    // if (1LL * n * k <= (int)1e8) sub12::solve();
    sub3::solve();
}

int32_t main() {
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    bool multitest = 0;
    int numTest = 1;
    if (multitest) cin >> numTest;

    while (numTest--) {
        solve();
    }

    return 0;
}

/* Lak lu theo dieu nhac!!!! */

컴파일 시 표준 에러 (stderr) 메시지

zarulje.cpp: In function 'int32_t main()':
zarulje.cpp:154:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zarulje.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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