oj.uz

Submission #314453

# Submission time Handle Problem Language Result Execution time Memory
314453 2020-10-20T00:36:55 Z thecodingwizard Žarulje (COI15_zarulje) C++11
100 / 100
 258 ms 9720 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1920 KB Output is correct
2 Correct 4 ms 1920 KB Output is correct
3 Correct 5 ms 1920 KB Output is correct
4 Correct 5 ms 2048 KB Output is correct
5 Correct 5 ms 1920 KB Output is correct
6 Correct 5 ms 2048 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 3192 KB Output is correct
2 Correct 207 ms 4984 KB Output is correct
3 Correct 213 ms 5168 KB Output is correct
4 Correct 217 ms 5240 KB Output is correct
5 Correct 217 ms 5628 KB Output is correct
6 Correct 225 ms 6776 KB Output is correct
7 Correct 223 ms 8056 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1920 KB Output is correct
2 Correct 4 ms 1920 KB Output is correct
3 Correct 5 ms 1920 KB Output is correct
4 Correct 5 ms 2048 KB Output is correct
5 Correct 5 ms 1920 KB Output is correct
6 Correct 5 ms 2048 KB Output is correct
7 Correct 109 ms 3192 KB Output is correct
8 Correct 207 ms 4984 KB Output is correct
9 Correct 213 ms 5168 KB Output is correct
10 Correct 217 ms 5240 KB Output is correct
11 Correct 217 ms 5628 KB Output is correct
12 Correct 225 ms 6776 KB Output is correct
13 Correct 223 ms 8056 KB Output is correct
14 Correct 15 ms 2304 KB Output is correct
15 Correct 129 ms 5112 KB Output is correct
16 Correct 246 ms 8184 KB Output is correct
17 Correct 237 ms 6776 KB Output is correct
18 Correct 254 ms 8568 KB Output is correct
19 Correct 237 ms 6648 KB Output is correct
20 Correct 254 ms 8696 KB Output is correct
21 Correct 258 ms 9720 KB Output is correct