Submission #1149417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149417		nrg_studio	Žarulje (COI15_zarulje)	C++20	100 / 100	107 ms	21064 KiB

zarulje

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

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define v vector

ll mod = 1e9+7;
ll mul(ll a, ll b) {return a*b%mod;}
void mul2(ll& a, ll b) {a = mul(a,b);}
ll exp(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) {res = mul(res,a);}
        a = mul(a,a);
        b /= 2;
    } return res;
}


const int MAX_N = 2e5;
int a[MAX_N], small_l[MAX_N+1], small_r[MAX_N+1], last[MAX_N], join[MAX_N];
v<int> comp[MAX_N];
ll ans[MAX_N+1];
ll fac[MAX_N+1], inv[MAX_N+1];

void calc() {
	fac[0] = 1;
	for (int i=1;i<MAX_N+1;i++) {fac[i] = mul(fac[i-1],i);}
	inv[MAX_N] = exp(fac[MAX_N],mod-2);
	for (int i=MAX_N;i;i--) {inv[i-1] = mul(inv[i],i);}
}

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

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    calc();
    int n, k; cin >> n >> k;

    stack<int> s, s2;
    for (int i=0;i<n;i++) {
        cin >> a[i]; a[i]--;
    }
    for (int i=0;i<n;i++) {
        while (s.size() && a[s.top()]>=a[i]) {s.pop();}
        small_l[i] = (s.empty() ? -1 : s.top());
        while (s2.size() && a[s2.top()]>=a[n-i-1]) {s2.pop();}
        small_r[n-i-1] = (s2.empty() ? n : s2.top());
        s.push(i); s2.push(n-i-1);

        last[a[i]] = n;
        ans[i] = 1;
        join[i] = -1;
    }
    
    small_l[n] = n+1; small_r[n] = 0;

    for (int i=n-1;i>=0;i--) {
        if (i<small_l[last[a[i]]]) {
            if (small_r[i]==small_l[last[a[i]]]) {join[last[a[i]]] = i;}
            last[a[i]] = i;
        }
        comp[last[a[i]]].pb(i);
    }

    for (int i=0;i<n;i++) {
        if (comp[i].empty()) {continue;}

        reverse(all(comp[i]));
        int m = comp[i].size();
        if (join[i]!=-1) {
            int tot = m+comp[join[i]].size();
            mul2(ans[small_l[i]],C(tot,m));
            mul2(ans[small_l[i]+1],exp(C(tot,m),mod-2));
        }
        for (int j=0;j<m;j++) {
            mul2(ans[comp[i][j]],C(m-1,j));
            mul2(ans[comp[i][j]+1],exp(C(m-1,j),mod-2));
            if (j && comp[i][j]-1 != comp[i][j-1]) {
                mul2(ans[comp[i][j-1]+1],C(m,j));
                mul2(ans[comp[i][j]],exp(C(m,j),mod-2));
            }
        }
    }
    for (int i=0;i<n;i++) {
        mul2(ans[i+1],ans[i]);
    }
    while (k--) {
        int p; cin >> p;
        cout << ans[p-1] << '\n';
    }

    /*
    assume this light is left of range
    then find nearest strictly small_ler value
    you can turn of until there,

    if an L and R range of same energy lightbulbs intersect, then any
    point inside them can reach this state, and has two options from here
    (biconditional)

    Find all components of L R intersection, then calc for each point and subrange
    in the component, with prefix multiplication/mod inverse division,

    and then sweep through once to get answer

    question: how to calc answer for a component
    have L points on left, R points on right

    it should be (L+R) choose L

    this means that we only need nearest small_ler values on either R or L
    */
}

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