Submission #283670

#	Time	Username	Problem	Language	Result	Execution time	Memory
283670		kdh9949	Žarulje (COI15_zarulje)	C++17	100 / 100	465 ms	145784 KiB

zarulje

#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 / 22
• Subtask 2: 38 / 38
• Subtask 3: 40 / 40