oj.uz

Submission #283670

# Submission time Handle Problem Language Result Execution time Memory
283670 2020-08-26T05:14:57 Z kdh9949 Žarulje (COI15_zarulje) C++17
100 / 100
 465 ms 145784 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define x first
#define y second
#define all(v) v.begin(),v.end()

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

  int n, q;
  cin >> n >> q;

  vint a(n + 2);
  for(int i = 1; i <= n; i++) cin >> a[i];

  const static ll M = ll(1e9) + 7;
  vll fa(n + 1, 1), fi(n + 1, 1);
  auto inv = [&](ll x) {
    ll r = 1;
    for(int k = M - 2; k; k /= 2, x = x * x % M) if(k & 1) r = r * x % M;
    return r;
  };
  for(int i = 1; i <= n; i++) {
    fa[i] = fa[i - 1] * i % M;
    fi[i] = inv(fa[i]);
  }
  auto com = [&](int n, int r) {
    if(n < 0 || r < 0 || r > n) return 0LL;
    return fa[n] * fi[r] % M * fi[n - r] % M;
  };

  const static int N = 200005;
  vll lc(N), rc(N);
  ll cans = 1;
  
  auto upd = [&](int p, int i, int v) {
    cans = cans * inv(com(lc[i] + rc[i], lc[i])) % M;
    (p ? rc : lc)[i] += v;
    cans = cans * com(lc[i] + rc[i], lc[i]) % M;
  };

  vector<stack<pii>> rhist(n + 1);
  stack<pii> rst;
  rst.emplace(n + 1, 1);
  for(int i = n; i >= 1; i--) {
    while(a[rst.top().x] > a[i]) {
      rhist[i].push(rst.top());
      upd(1, a[rst.top().x], -rst.top().y);
      rst.pop();
    }
    if(a[rst.top().x] == a[i]) {
      rhist[i].emplace(-1, 0);
      rst.top().y++;
    }
    else {
      rhist[i].emplace(-2, 0);
      rst.emplace(i, 1);
    }
    upd(1, a[rst.top().x], 1);
  }

  vll ans(n + 1);
  stack<pii> lst;
  lst.emplace(0, 1);
  for(int i = 1; i <= n; i++) {
    while(!rhist[i].empty()) {
      pii cur = rhist[i].top();
      rhist[i].pop();
      if(cur.x == -1) {
        rst.top().y--;
        upd(1, a[rst.top().x], -1);
      }
      else if(cur.x == -2) {
        upd(1, a[rst.top().x], -1);
        rst.pop();
      }
      else {
        rst.push(cur);
        upd(1, a[cur.x], cur.y);
      }
    }

    ans[i] = cans;

    while(a[lst.top().x] > a[i]) {
      upd(0, a[lst.top().x], -lst.top().y);
      lst.pop();
    }
    if(a[lst.top().x] == a[i]) lst.top().y++;
    else lst.emplace(i, 1);
    upd(0, a[lst.top().x], 1);
  }

  while(q--) {
    int x;
    cin >> x;
    cout << ans[x] << '\n';
  }

  return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3584 KB Output is correct
2 Correct 4 ms 4224 KB Output is correct
3 Correct 6 ms 4864 KB Output is correct
4 Correct 6 ms 4864 KB Output is correct
5 Correct 7 ms 4864 KB Output is correct
6 Correct 6 ms 4864 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 73720 KB Output is correct
2 Correct 342 ms 143644 KB Output is correct
3 Correct 368 ms 143992 KB Output is correct
4 Correct 378 ms 143864 KB Output is correct
5 Correct 382 ms 143700 KB Output is correct
6 Correct 412 ms 143864 KB Output is correct
7 Correct 431 ms 143736 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3584 KB Output is correct
2 Correct 4 ms 4224 KB Output is correct
3 Correct 6 ms 4864 KB Output is correct
4 Correct 6 ms 4864 KB Output is correct
5 Correct 7 ms 4864 KB Output is correct
6 Correct 6 ms 4864 KB Output is correct
7 Correct 204 ms 73720 KB Output is correct
8 Correct 342 ms 143644 KB Output is correct
9 Correct 368 ms 143992 KB Output is correct
10 Correct 378 ms 143864 KB Output is correct
11 Correct 382 ms 143700 KB Output is correct
12 Correct 412 ms 143864 KB Output is correct
13 Correct 431 ms 143736 KB Output is correct
14 Correct 23 ms 10752 KB Output is correct
15 Correct 211 ms 74748 KB Output is correct
16 Correct 383 ms 145760 KB Output is correct
17 Correct 399 ms 144684 KB Output is correct
18 Correct 414 ms 145784 KB Output is correct
19 Correct 425 ms 144248 KB Output is correct
20 Correct 431 ms 144120 KB Output is correct
21 Correct 465 ms 144272 KB Output is correct