| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 896470 |
2024-01-01T14:02:05 Z |
Alcabel |
Žarulje (COI15_zarulje) |
C++17 |
|
176 ms |
26120 KB |
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
struct Modint {
int x;
Modint() {
x = 0;
}
Modint(int _x) {
while (_x >= mod) {
_x -= mod;
}
while (_x < 0) {
_x += mod;
}
x = _x;
}
Modint(long long _x) {
if (_x >= mod || _x <= -mod) {
_x %= mod;
}
if (_x < 0) {
_x += mod;
}
x = _x;
}
Modint operator+(const Modint& other) const {
return Modint(x + other.x);
}
Modint operator*(const Modint& other) const {
return Modint(x * 1ll * other.x);
}
void operator+=(const Modint& other) {
*this = *this + other;
}
void operator*=(const Modint& other) {
*this = *this * other;
}
Modint operator^(long long p) const {
Modint res = 1, tmp = x;
while (p > 0) {
if (p & 1) {
res *= tmp;
}
tmp *= tmp;
p >>= 1;
}
return res;
}
Modint operator/(const Modint& other) const {
return *this * (other ^ (mod - 2));
}
void operator/=(const Modint& other) {
*this = *this / other;
}
~Modint() {}
};
vector<Modint> fact, invFact;
void buildFact(int n) {
fact.resize(n + 1);
invFact.resize(n + 1);
fact[0] = 1;
for (int i = 1; i <= n; ++i) {
fact[i] = fact[i - 1] * i;
// cerr << "i: " << i << ", fact: " << fact[i].x << '\n';
}
invFact[n] = fact[n] ^ (mod - 2);
for (int i = n; i > 0; --i) {
invFact[i - 1] = invFact[i] * i;
}
}
Modint C(int n, int k) {
if (n < 0 || k < 0 || n < k) {
return 0;
}
return fact[n] * invFact[k] * invFact[n - k];
}
void solve() {
int n, k;
cin >> n >> k;
buildFact(n);
// cerr << C(n, n / 2).x << '\n';
vector<int> a(n), order(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
order[i] = i;
}
sort(order.begin(), order.end(), [&](const int& A, const int& B) {
return make_pair(a[A], A) < make_pair(a[B], B);
});
vector<vector<int>> byVal(n);
int difs = 0;
for (int l = 0, r; l < n; ++l, ++difs) {
r = l - 1;
while (r + 1 < n && a[order[r + 1]] == a[order[l]]) {
++r;
byVal[difs].emplace_back(order[r]);
}
l = r;
}
vector<Modint> ans(n, 1);
set<int> borders = {-1, n};
vector<Modint> modif(n, 1);
for (int val = 0; val < difs; ++val) {
int sz = byVal[val].size();
// cerr << "val: " << a[byVal[val][0]] << '\n';
for (int pos = 0, posL = 0, posR = 0; pos < sz; ++pos) {
// cerr << "idx: " << byVal[val][pos] << '\n';
auto it = borders.upper_bound(byVal[val][pos]);
int bR = *it, bL = *(--it);
while (byVal[val][posL] <= bL) {
++posL;
}
while (posR < sz && byVal[val][posR] < bR) {
++posR;
}
// cerr << "posL: " << posL << ", posR: " << posR << '\n';
assert(posL <= pos && pos < posR);
ans[byVal[val][pos]] *= C(posR - posL - 1, pos - posL);
// cerr << ans[byVal[val][pos]].x << '\n';
if (pos != 0) {
if (byVal[val][pos - 1] > bL) {
// [byVal[val][pos - 1] + 1, byVal[val][pos] - 1]
modif[byVal[val][pos - 1] + 1] *= C(posR - posL, posR - pos);
modif[byVal[val][pos]] /= C(posR - posL, posR - pos);
} else if (it != borders.begin() && *prev(it) < byVal[val][pos - 1]) {
int prevPosL = upper_bound(byVal[val].begin(), byVal[val].end(), *prev(it)) - byVal[val].begin();
// cerr << "!\n";
// cerr << "prevPosL: " << prevPosL << '\n';
ans[bL] *= C(posR - prevPosL, posR - pos);
}
}
}
// cerr << "modif: " << modif[0].x << '\n';
for (const int& i : byVal[val]) {
borders.insert(i);
}
}
Modint tmp = 1;
for (int i = 0; i < n; ++i) {
tmp *= modif[i];
// cerr << "i: " << i << ", tmp: " << tmp.x << '\n';
ans[i] *= tmp;
}
while (k--) {
int pos;
cin >> pos;
--pos;
cout << ans[pos].x << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
10556 KB |
Output is correct |
| 2 |
Correct |
87 ms |
20252 KB |
Output is correct |
| 3 |
Correct |
99 ms |
20564 KB |
Output is correct |
| 4 |
Correct |
122 ms |
20824 KB |
Output is correct |
| 5 |
Correct |
124 ms |
21332 KB |
Output is correct |
| 6 |
Correct |
176 ms |
23172 KB |
Output is correct |
| 7 |
Correct |
133 ms |
24392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
53 ms |
10556 KB |
Output is correct |
| 8 |
Correct |
87 ms |
20252 KB |
Output is correct |
| 9 |
Correct |
99 ms |
20564 KB |
Output is correct |
| 10 |
Correct |
122 ms |
20824 KB |
Output is correct |
| 11 |
Correct |
124 ms |
21332 KB |
Output is correct |
| 12 |
Correct |
176 ms |
23172 KB |
Output is correct |
| 13 |
Correct |
133 ms |
24392 KB |
Output is correct |
| 14 |
Correct |
6 ms |
1624 KB |
Output is correct |
| 15 |
Correct |
65 ms |
12136 KB |
Output is correct |
| 16 |
Correct |
119 ms |
23708 KB |
Output is correct |
| 17 |
Correct |
118 ms |
22296 KB |
Output is correct |
| 18 |
Correct |
165 ms |
24148 KB |
Output is correct |
| 19 |
Correct |
138 ms |
22408 KB |
Output is correct |
| 20 |
Correct |
176 ms |
24648 KB |
Output is correct |
| 21 |
Correct |
159 ms |
26120 KB |
Output is correct |
