Submission #314453

#	Time	Username	Problem	Language	Result	Execution time	Memory
314453		thecodingwizard	Žarulje (COI15_zarulje)	C++11	100 / 100	258 ms	9720 KiB

zarulje

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int mod = 1000000007;

int ctLeft[200001], ctRight[200001];
bool included[200001];
int ans[200001];
int change[200001];
ll fac[200001];

ll power(ll x, int y, int p)
{ 
    ll res = 1; // Initialize result 
  
    x = x % p; // Update x if it is more than or 
    // equal to p 
  
    while (y > 0) { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res * x) % p; 
  
        // y must be even now 
        y = y >> 1; // y = y/2 
        x = (x * x) % p; 
    } 
    return res; 
}

ll inv(ll x) {
    return power(x, mod-2, mod);
}

// calculate addition to ans based on x
// make sure to update change
ll calc(int x) {
    if (ctLeft[x] > 0 && ctRight[x] > 0) {
        //cout << "changing " << x << " = " << ctLeft[x] << ", " << ctRight[x] << endl;
        return change[x] = fac[ctLeft[x]+ctRight[x]] * inv(fac[ctRight[x]]) % mod * inv(fac[ctLeft[x]]) % mod;
    } else {
        return change[x] = 1;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, k; cin >> n >> k;
    int A[n]; for (int i = 0; i < n; i++) cin >> A[i];

    for (int i = 0; i <= 200000; i++) {
        fac[i] = i == 0 ? 1 : (fac[i-1]*i)%mod;
    }

    int nextRight[n];
    stack<int> s;
    for (int i = 0; i < n; i++) {
        nextRight[i] = n;
        while (!s.empty() && A[s.top()] >= A[i]) {
            nextRight[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }

    s = stack<int>();

    set<int> changed;
    ll runningAns = 1;
    for (int i = 0; i < n; i++) {
        //cout << "i is " << i << endl;
        int rptr = i+1;
        while (rptr < n && !included[rptr]) {
            included[rptr] = true;
            ctRight[A[rptr]]++;
            changed.insert(A[rptr]);
            rptr = nextRight[rptr];
        }
        if (i != 0) {
            int prevptr = i;
            while (prevptr < n && prevptr != rptr) {
                included[prevptr] = false;
                ctRight[A[prevptr]]--;
                changed.insert(A[prevptr]);
                prevptr = nextRight[prevptr];
            }
        }
        for (int c : changed) {
            //cout << "upd " << c << endl;
            runningAns = (runningAns * (change[c] == 0 ? 1 : inv(change[c])) % mod * calc(c)) % mod;
            //cout << c << ": " << change[c] << endl;
        }

        ans[i] = runningAns;
        
        changed.clear();
        while (!s.empty() && A[s.top()] > A[i]) {
            ctLeft[A[s.top()]]--;
            changed.insert(A[s.top()]);
            s.pop();
        }
        ctLeft[A[i]]++;
        changed.insert(A[i]);
        s.push(i);
    }

    for (int i = 0; i < k; i++) {
        int x; cin >> x; --x;
        cout << ans[x] << "\n";
    }

    return 0;
}

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