| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 330849 |
2020-11-26T18:25:21 Z |
Falcon |
Žarulje (COI15_zarulje) |
C++17 |
|
120 ms |
3876 KB |
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.hpp"
#endif
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N) for(int i = 0; i < (N); ++i)
#define rrep(i, N) for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N) for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e) for(int i = (s); i <= (e); ++i)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#ifdef DEBUG
#define debug(x...) { \
++dbg::depth; \
string dbg_vals = dbg::to_string(x); \
--dbg::depth; \
dbg::fprint(__func__, __LINE__, #x, dbg_vals); \
}
#define light_debug(x) { \
dbg::light = true; \
dbg::dout << __func__ << ":" << __LINE__; \
dbg::dout << " " << #x << " = " << x << endl; \
dbg::light = false; \
}
#else
#define debug(x...) 42
#define light_debug(x) 42
#endif
using ll = long long;
template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }
template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }
class Modular {
int value;
public:
static int mod;
Modular(long long x = 0) {
value = (int)((x % mod + mod) % mod);
}
inline Modular& operator +=(Modular x) {
value += x.value;
if(value >= mod) value -= mod;
return *this;
}
inline Modular& operator -=(Modular x) {
value -= x.value;
if(value < 0) value += mod;
return *this;
}
inline Modular& operator *=(Modular x) {
value = int((long long)x.value * value % mod);
return *this;
}
// TODO : Make this Extended Euclid to handle composite moduli.
inline Modular& operator /=(Modular x) {
return *this *= x.pow(-1);
}
inline Modular operator -() const {
return Modular(-value);
}
inline Modular& operator ++() {
return *this += 1;
}
inline Modular& operator --() {
return *this -= 1;
}
inline Modular operator ++(int) {
Modular t{*this};
*this += 1;
return t;
}
inline Modular operator --(int) {
Modular t{*this};
*this -= 1;
return t;
}
Modular pow(long long n) const {
while(n < 0) n += mod - 1;
Modular v(1), a(value);
for(; n; a *= a, n >>= 1)
if(n & 1) v *= a;
return v;
}
inline Modular operator +(Modular x) const {
return x += *this;
}
inline Modular operator -(Modular x) const {
return *this + (-x);
}
inline Modular operator *(Modular x) const {
return x *= *this;
}
inline Modular operator /(Modular x) const {
return (*this) * x.pow(-1);
}
inline bool operator ==(Modular x) const {
return value == x.value;
}
inline bool operator !=(Modular x) const {
return value != x.value;
}
inline explicit operator int() const {
return value;
}
Modular fact() const {
Modular x(1);
for(int i = 1; i <= value; ++i) x *= i;
return x;
}
friend ostream& operator <<(ostream& os, Modular x) {
return os << x.value;
}
friend istream& operator >>(istream& is, Modular& x) {
is >> x.value; x.value %= mod; return is;
}
};
int Modular::mod{1000000007};
namespace combinatorics {
constexpr int MAXN{200000};
array<Modular, MAXN + 1> fact, ifact;
void init() {
fact[0] = ifact[0] = 1;
for(int i = 1; i <= MAXN; ++i)
fact[i] = fact[i - 1] * i, ifact[i] = fact[i].pow(-1);
}
inline Modular nCr(int n, int r) {
return fact[n] * ifact[n - r] * ifact[r];
}
inline Modular nPr(int n, int r) {
return fact[n] * ifact[n - r];
}
} // namespace combinatorics
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifdef DEBUG
freopen("debug", "w", stderr);
#endif
combinatorics::init();
int N, K; cin >> N >> K;
vector<int> A(N); for(int& a : A) cin >> a;
vector<int> P(K); for(int& p : P) cin >> p, --p;
assert(ll(N) * K <= 2000 * 2000);
auto get_suffix = [&](int p) {
queue<int> v;
for(int i = p; i < N;) {
int x{A[i++]};
for(; i < N && A[i] > x; ++i);
v.push(x);
}
return v;
};
auto get_prefix = [&](int p) {
queue<int> v;
for(int i = p; i >= 0;) {
int x{A[i--]};
for(; i >= 0 && A[i] > x; --i);
v.push(x);
}
return v;
};
auto solve_for = [&](int p) {
queue<int> pref{get_prefix(p - 1)};
queue<int> suff{get_suffix(p + 1)};
Modular ans{1};
while(!pref.empty() && !suff.empty()) {
int l{}, r{}, x{max(pref.front(), suff.front())};
while(!pref.empty() && pref.front() == x) ++l, pref.pop();
while(!suff.empty() && suff.front() == x) ++r, suff.pop();
ans *= combinatorics::nCr(l + r, r);
}
return ans;
};
for(int& p : P) cout << solve_for(p) << '\n';
#ifdef DEBUG
dbg::dout << "\nExecution time: " << clock() * 1000 / CLOCKS_PER_SEC << "ms" << endl;
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
1900 KB |
Output is correct |
| 2 |
Correct |
100 ms |
2028 KB |
Output is correct |
| 3 |
Correct |
108 ms |
1900 KB |
Output is correct |
| 4 |
Correct |
103 ms |
1900 KB |
Output is correct |
| 5 |
Correct |
101 ms |
1900 KB |
Output is correct |
| 6 |
Correct |
103 ms |
2028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
2340 KB |
Output is correct |
| 2 |
Correct |
114 ms |
2796 KB |
Output is correct |
| 3 |
Correct |
115 ms |
2668 KB |
Output is correct |
| 4 |
Correct |
115 ms |
2668 KB |
Output is correct |
| 5 |
Correct |
118 ms |
2668 KB |
Output is correct |
| 6 |
Correct |
118 ms |
2668 KB |
Output is correct |
| 7 |
Correct |
120 ms |
2668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
1900 KB |
Output is correct |
| 2 |
Correct |
100 ms |
2028 KB |
Output is correct |
| 3 |
Correct |
108 ms |
1900 KB |
Output is correct |
| 4 |
Correct |
103 ms |
1900 KB |
Output is correct |
| 5 |
Correct |
101 ms |
1900 KB |
Output is correct |
| 6 |
Correct |
103 ms |
2028 KB |
Output is correct |
| 7 |
Correct |
110 ms |
2340 KB |
Output is correct |
| 8 |
Correct |
114 ms |
2796 KB |
Output is correct |
| 9 |
Correct |
115 ms |
2668 KB |
Output is correct |
| 10 |
Correct |
115 ms |
2668 KB |
Output is correct |
| 11 |
Correct |
118 ms |
2668 KB |
Output is correct |
| 12 |
Correct |
118 ms |
2668 KB |
Output is correct |
| 13 |
Correct |
120 ms |
2668 KB |
Output is correct |
| 14 |
Runtime error |
105 ms |
3876 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 15 |
Halted |
0 ms |
0 KB |
- |
