Submission #653768

#TimeUsernameProblemLanguageResultExecution timeMemory
653768GusterGoose27Žarulje (COI15_zarulje)C++11
0 / 100
181 ms17896 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; typedef long long ll; const int MOD = 1e9+7; const int MAXN = 2e5+4; int powers[MAXN]; int dp[MAXN]; int skip_dp[MAXN]; int ans[MAXN]; int fac[MAXN]; int facinv[MAXN]; pii cur_space[MAXN]; int n, q; int bash(pii range) { if (range == pii(1, n-2)) return 1; if (powers[range.first-1] == powers[range.second+1]) return (bash(pii(range.first-1, range.second))+bash(pii(range.first, range.second+1)) % MOD); if (powers[range.first-1] > powers[range.second+1]) return bash(pii(range.first-1, range.second)); return bash(pii(range.first, range.second+1)); } int expo(ll a, int b) { ll res = 1; while (b > 0) { if (b & 1) { res *= a; res %= MOD; } b >>= 1; a *= a; a %= MOD; } return res; } int c(int n, int k) { ll cur = fac[n]; cur *= facinv[k]; cur %= MOD; cur *= facinv[n-k]; return (cur%MOD); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> q; n += 2; fac[0] = 1; ll cur = 1; facinv[0] = 1; for (int i = 1; i <= n; i++) { cur *= i; cur %= MOD; fac[i] = cur; facinv[i] = expo(fac[i], MOD-2); } powers[0] = 0; powers[n-1] = 0; vector<pii> proc_order; for (int i = 1; i < n-1; i++) { cin >> powers[i]; assert(powers[i] > 0); proc_order.push_back(pii(powers[i], i)); } sort(proc_order.begin(), proc_order.end()); set<int> completed_vals; dp[0] = dp[n-1] = 1; completed_vals.insert(0); completed_vals.insert(n-1); for (int r = 0; r < n-2;) { vector<int> to_add; vector<int> extra_consid; int l = r; while (r < n-2 && proc_order[l].first == proc_order[r].first) r++; for (int curr = l; curr < r;) { int curl = curr; auto it = completed_vals.upper_bound(proc_order[curl].second); int rp = *it; it--; int lp = *it; vector<int> cur_posses; while (curr < r && *completed_vals.upper_bound(proc_order[curr].second) == rp) { cur_posses.push_back(proc_order[curr].second); to_add.push_back(proc_order[curr].second); curr++; } cur_space[rp].first = cur_space[lp].second = cur_posses.size(); extra_consid.push_back(lp); extra_consid.push_back(rp); for (int p = 0; p < cur_posses.size(); p++) { int i = cur_posses[p]; ll curdp = dp[lp]; curdp *= c(cur_posses.size(), p+1); curdp %= MOD; dp[i] = curdp; curdp = dp[lp]; curdp *= c(cur_posses.size()-1, p); curdp %= MOD; ans[i] = curdp; if (p < cur_posses.size()-1) { curdp = dp[lp]; curdp *= c(cur_posses.size()-1, p+1); curdp %= MOD; skip_dp[i] = curdp; } } } for (int m: extra_consid) { if (cur_space[m].first != 0 && cur_space[m].second != 0) { auto it = completed_vals.lower_bound(m); int lp = *(--it); ll curdp; if (powers[lp] == powers[m]) curdp = skip_dp[lp]; else curdp = dp[lp]; curdp *= c(cur_space[m].first+cur_space[m].second, cur_space[m].first); curdp %= MOD; ans[m] = curdp; } cur_space[m] = pii(0, 0); } for (int v: to_add) completed_vals.insert(v); } bool fail = 0; for (int i = 0; i < q; i++) { int x; cin >> x; //int b = bash(pii(x, x)); cout << ans[x] << /*" " << b << */"\n"; //if (b != ans[x]) fail = 1; } if (fail) cout << "FAIL\n"; }

Compilation message (stderr)

zarulje.cpp: In function 'int main()':
zarulje.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    for (int p = 0; p < cur_posses.size(); p++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~
zarulje.cpp:105:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     if (p < cur_posses.size()-1) {
      |         ~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...