Submission #330849

#TimeUsernameProblemLanguageResultExecution timeMemory
330849FalconŽarulje (COI15_zarulje)C++17
60 / 100
120 ms3876 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...