oj.uz

Submission #21033

# Submission time Handle Problem Language Result Execution time Memory
21033 2017-03-30T08:10:03 Z model_code Žarulje (COI15_zarulje) C++11
100 / 100
 219 ms 56428 KB 
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <stack>

using namespace std;

typedef long long llint;

const int MAXN = 1000100;
const int mod = 1e9 + 7;

int mul(int a, int b) {
  return llint(a)*b % mod;
}

int powmod(int a, int b) {
  if (b == 0) return 1;
  if (b&1) return mul(a, powmod(a, b-1));
  return powmod(mul(a, a), b/2);
}

int f[MAXN], invf[MAXN];
int a[MAXN], ans[MAXN];
int fl[MAXN], fr[MAXN];
vector<pair<int, int>> e[MAXN];

void add(int &a, int b, int d, int &ways) {
  ways = mul(ways, mul(f[a], mul(f[b], invf[a+b])));
  a += d;
  ways = mul(ways, mul(invf[a], mul(invf[b], f[a+b])));
}

int main(void) {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; ++i)
    scanf("%d", &a[i]);
  
  f[0] = invf[0] = 1;
  for (int i = 1; i <= n; ++i) {
    f[i] = mul(f[i-1], i);
    invf[i] = powmod(f[i], mod-2);
  }

  stack<int> S;
  for (int i = n-1; i >= 0; --i) {
    while (!S.empty() && S.top() > a[i]) {
      fr[S.top()]--;
      e[i].push_back({S.top(), +1});
      S.pop();
    }
    e[i].push_back({a[i], -1});
    fr[a[i]]++;
    S.push(a[i]);
  }
  while (!S.empty()) S.pop();

  int ways = 1;
  for (int i = 0; i < n; ++i) {
    for (auto &p: e[i])
      add(fr[p.first], fl[p.first], p.second, ways);    
    ans[i] = ways;

    while (!S.empty() && S.top() > a[i]) {
      add(fl[S.top()], fr[S.top()], -1, ways);
      S.pop();
    }
    add(fl[a[i]], fr[a[i]], +1, ways);
    S.push(a[i]);
  }
  
  for (int i = 0; i < k; ++i) {
    int p;
    scanf("%d", &p); --p;
    printf("%d\n", ans[p]);
  }
  return 0;
}

Compilation message

zarulje.cpp: In function 'int main()':
zarulje.cpp:37:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &k);
                         ^
zarulje.cpp:39:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
                       ^
zarulje.cpp:76:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p); --p;
                    ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 48904 KB Output is correct
2 Correct 9 ms 48904 KB Output is correct
3 Correct 13 ms 49036 KB Output is correct
4 Correct 3 ms 49036 KB Output is correct
5 Correct 6 ms 49036 KB Output is correct
6 Correct 6 ms 49036 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 52600 KB Output is correct
2 Correct 123 ms 56416 KB Output is correct
3 Correct 113 ms 56424 KB Output is correct
4 Correct 129 ms 56424 KB Output is correct
5 Correct 136 ms 56428 KB Output is correct
6 Correct 146 ms 56428 KB Output is correct
7 Correct 159 ms 56428 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 48904 KB Output is correct
2 Correct 9 ms 48904 KB Output is correct
3 Correct 13 ms 49036 KB Output is correct
4 Correct 3 ms 49036 KB Output is correct
5 Correct 6 ms 49036 KB Output is correct
6 Correct 6 ms 49036 KB Output is correct
7 Correct 66 ms 52600 KB Output is correct
8 Correct 123 ms 56416 KB Output is correct
9 Correct 113 ms 56424 KB Output is correct
10 Correct 129 ms 56424 KB Output is correct
11 Correct 136 ms 56428 KB Output is correct
12 Correct 146 ms 56428 KB Output is correct
13 Correct 159 ms 56428 KB Output is correct
14 Correct 19 ms 49300 KB Output is correct
15 Correct 93 ms 52600 KB Output is correct
16 Correct 169 ms 56292 KB Output is correct
17 Correct 153 ms 56424 KB Output is correct
18 Correct 169 ms 56428 KB Output is correct
19 Correct 159 ms 56428 KB Output is correct
20 Correct 203 ms 56428 KB Output is correct
21 Correct 219 ms 56428 KB Output is correct