Submission #636684

#	Time	Username	Problem	Language	Result	Execution time	Memory
636684		abeker	Žarulje (COI15_zarulje)	C++17	60 / 100	1079 ms	3900 KiB

zarulje

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
const int MOD = 1e9 + 7;

int N, K;
int a[MAXN];
int fact[MAXN], inv[MAXN];

void load() {
  scanf("%d%d", &N, &K);
  for (int i = 1; i <= N; i++)
    scanf("%d", a + i);
}

inline int mul(int x, int y) {
  return (long long)x * y % MOD;
}

int pot(int x, int y) {
  int res = 1;
  for (; y; y /= 2) {
    if (y % 2)
      res = mul(res, x);
    x = mul(x, x);
  }
  return res;
}

void solve() {
  fact[0] = inv[0] = 1;
  for (int i = 1; i <= N; i++) {
    fact[i] = mul(fact[i - 1], i);
    inv[i] = pot(fact[i], MOD - 2);
  }
  while (K--) {
    int p;
    scanf("%d", &p);
    int ans = 1;
    int l = p - 1, r = p + 1;
    while (l >= 1 || r <= N) {
      int nxt_l = l, nxt_r = r;
      bool larger_left = a[l] >= a[r];
      bool larger_right = a[r] >= a[l];
      int equal_left = 0, equal_right = 0;
      if (larger_left)
        for (; a[nxt_l] >= a[l]; nxt_l--)
          equal_left += a[nxt_l] == a[l];
      if (larger_right)
        for (; a[nxt_r] >= a[r]; nxt_r++)
          equal_right += a[nxt_r] == a[r];
      if (larger_left && larger_right)
        ans = mul(ans, mul(fact[equal_left + equal_right], mul(inv[equal_left], inv[equal_right])));
      l = nxt_l;
      r = nxt_r;
    }
    printf("%d ", ans);
  }
  puts("");
}

int main() {
  load();
  solve();
  return 0;
}

Compilation message (stderr)

zarulje.cpp: In function 'void load()':
zarulje.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   scanf("%d%d", &N, &K);
      |   ~~~~~^~~~~~~~~~~~~~~~
zarulje.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d", a + i);
      |     ~~~~~^~~~~~~~~~~~~
zarulje.cpp: In function 'void solve()':
zarulje.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d", &p);
      |     ~~~~~^~~~~~~~~~

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