Submission #283649

#	Time	Username	Problem	Language	Result	Execution time	Memory
283649		kdh9949	Žarulje (COI15_zarulje)	C++17	60 / 100	1092 ms	5628 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;
  };

  while(q--) {
    int x;
    cin >> x;

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

    ll ans = 1;
    while(a[lst.top().x] && a[rst.top().x]) {
      int lv = a[lst.top().x], rv = a[rst.top().x];
      if(lv > rv) lst.pop();
      else if(lv < rv) rst.pop();
      else {
        ans = ans * com(lst.top().y + rst.top().y, lst.top().y) % M;
        lst.pop();
        rst.pop();
      }
    }
    cout << ans << '\n';
  }

  return 0;
}

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