author: exhausted, developer: exhausted
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
std::sort(a.begin(), a.end());
int p = (n + 1) / 2 - 1;
int res = std::count(a.begin() + p, a.end(), a[p]);
std::cout << res << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t = 1;
std::cin >> t;
while (t--) {
solve();
}
}
author: max0000561, developer: yunetive29
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int P = 1e9 + 7;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int S = 0, sum = 0;
int cur = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
cur += a[i];
cur = max(cur, 0LL);
S = max(S, cur);
}
sum = (sum % P + P) % P;
S = S % P;
int t = 1;
for (int i = 0; i < k; i++) {
t = t * 2 % P;
}
int ans = (sum + S * t - S + P) % P;
cout << ans << '\n';
}
signed main() {
//cout << fixed << setprecision(20);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1, G = 1;
//cin >> G;
cin >> T;
while (T--)
solve();
return 0;
}
author: exhausted, developer: exhausted
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n, k;
std::cin >> n >> k;
std::vector<std::vector<int>> adj(n);
for (int i = 0; i < n - 1; i++) {
int v, u;
std::cin >> v >> u;
--v, --u;
adj[v].emplace_back(u);
adj[u].emplace_back(v);
}
auto check = [&](int x) {
int res = 0;
auto dfs = [&](auto self, int v, int f) -> int {
int sz = 1;
for (int u : adj[v]) {
if (u == f) {
continue;
}
sz += self(self, u, v);
}
if (sz >= x && f != v) {
++res, sz = 0;
}
return sz;
};
int t = dfs(dfs, 0, 0);
return (res > k || (t >= x && res == k) ? true : false);
};
int low = 1, high = n / (k + 1) + 1;
while (high - low > 1) {
int mid = (low + high) / 2;
if (check(mid)) {
low = mid;
} else {
high = mid;
}
}
std::cout << low << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t = 1;
std::cin >> t;
while (t--) {
solve();
}
}
author: azureglow, developer: azureglow
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define all(a) a.begin(), a.end()
void solve() {
int n, x;
cin >> n >> x;
++x;
vector<int> a(n);
for (int &i: a)
cin >> i;
int res = -1;
for (int i = 30; i >= 0; --i) {
vector<int> b;
bool open = false;
for (int j = 0; j < a.size(); ++j) {
if (!open)
b.push_back(a[j]);
else
b.back() ^= a[j];
if (a[j] & (1 << i))
open = !open;
}
if (!(x & (1 << i))) {
if (open) {
cout << res << '\n';
return;
}
a = b;
} else {
if (!open)
res = max(res, (int) b.size());
}
}
cout << res << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
}
Solution (74TrAkToR)
#include<bits/stdc++.h>
using namespace std;
int const maxn = 1e5 + 5;
int a[maxn];
int solve(int n, int x) {
int res = 0, curr = 0;
for (int i = 1; i <= n; i++) {
curr ^= a[i];
if ((curr|x) == x) curr = 0, res++;
else {
if (i == n) return -1;
}
}
return res;
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, x;
cin >> n >> x;
for (int i = 1; i <= n; i++) cin >> a[i];
int ans = -1;
ans = max(ans, solve(n, x));
for (int b = 29; b >= 0; b--) {
if ((x>>b)&1) {
int y = (x^(1 << b));
for (int c = b - 1; c >= 0; c--) {
if (((y>>c)&1) == 0) y ^= (1 << c);
}
ans = max(ans, solve(n, y));
}
}
cout << ans << '\n';
}
return 0;
}
author: yunetive29, developer: yunetive29
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
template<int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(i64 x) : x{norm(x % P)} {}
constexpr int norm(int x) const {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(P - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, P - 2);
}
constexpr MInt &operator*=(MInt rhs) {
x = 1LL * x * rhs.x % P;
return *this;
}
constexpr MInt &operator+=(MInt rhs) {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
constexpr int MOD = 1e9 + 7;
using Z = MInt<MOD>;
namespace comb {
int n = 0;
std::vector<Z> _fac = {1};
std::vector<Z> _invfac = {1};
std::vector<Z> _inv = {0};
void init(int m) {
if (m <= n) return;
_fac.resize(m + 1);
_invfac.resize(m + 1);
_inv.resize(m + 1);
for (int i = n + 1; i <= m; i++) {
_fac[i] = _fac[i - 1] * i;
}
_invfac[m] = _fac[m].inv();
for (int i = m; i > n; i--) {
_invfac[i - 1] = _invfac[i] * i;
_inv[i] = _invfac[i] * _fac[i - 1];
}
n = m;
}
Z fac(int m) {
if (m > n) init(2 * m);
return _fac[m];
}
Z invfac(int m) {
if (m > n) init(2 * m);
return _invfac[m];
}
Z inv(int m) {
if (m > n) init(2 * m);
return _inv[m];
}
Z binom(int m, int k) {
if (m < k || k < 0) return 0;
return fac(m) * invfac(k) * invfac(m - k);
}
} // namespace comb
void solve() {
int n, m1, m2;
std::cin >> n >> m1 >> m2;
std::vector<int> p(m1), s(m2);
for (int i = 0; i < m1; i++) {
std::cin >> p[i];
}
for (int i = 0; i < m2; i++) {
std::cin >> s[i];
}
if (p[0] != 1 || s[0] != p[m1 - 1] || s[m2 - 1] != n) {
std::cout << "0\n";
return;
}
Z res = comb::binom(n - 1, s[0] - 1);
for (int i = m1 - 2; i > -1; i--) {
res *= comb::binom(p[i + 1] - 2, p[i + 1] - p[i] - 1) * comb::fac(p[i + 1] - p[i] - 1);
}
for (int i = 1; i < m2; i++) {
res *= comb::binom(n - s[i - 1] - 1, s[i] - s[i - 1] - 1) * comb::fac(s[i] - s[i - 1] - 1);
}
std::cout << res << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("/home/q1n/coding/input.txt", "r", stdin);
freopen("/home/q1n/coding/output.txt", "w", stdout);
#else
// online submission
#endif
int t = 1;
std::cin >> t;
while (t--) {
solve();
}
}
author: exhausted, yunetive29, developer: exhausted, yunetive29
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using i64 = long long;
template<class Info>
struct Fenwick {
std::vector<Info> t;
int n;
Fenwick(int n = 0) : n(n) {
t.resize(n);
}
void add(int x, const Info &v) {
for (int i = x + 1; i <= n; i += i & -i) {
t[i - 1] = t[i - 1] + v;
}
}
Info sum(int x) {
x++;
Info res = Info();
for (int i = x; i > 0; i -= i & -i) {
res = res + t[i - 1];
}
return res;
}
Info rangeSum(int l, int r) {
Info res = sum(r) - sum(l - 1);
return res;
}
};
void solve() {
int n, q;
std::cin >> n >> q;
std::vector<int> a(n), pos(n + 1);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
std::reverse(a.begin(), a.end());
for (int i = 0; i < n; i++) {
pos[a[i]] = i;
}
constexpr int K = 19;
std::vector<i64> res(q);
std::vector<std::vector<std::pair<int, int>>> qry(n);
for (int i = 0; i < q; i++) {
int l, r;
std::cin >> l >> r;
l--, r--;
std::swap(l, r);
l = n - l - 1;
r = n - r - 1;
qry[r].emplace_back(l, i);
}
std::vector<i64> dp(n + 1);
Fenwick<i64> f(n);
for (int r = 0; r < n; r++) {
int x = a[r];
dp[x] = 1;
// n * log(n) * log(n)
for (int y = x; y <= n; y += x) {
if (pos[y] > pos[x]) {
continue;
}
for (int z = 2 * y; z <= n; z += y) {
if (pos[z] > pos[y]) {
continue;
}
dp[z] += dp[y];
}
}
// n * log(n) * log(n)
for (int y = x; y <= n; y += x) {
f.add(pos[y], dp[y]);
dp[y] = 0;
}
// q * log(n)
for (auto [l, i] : qry[r]) {
res[i] += f.rangeSum(l, r);
}
}
for (int i = 0; i < q; i++) {
std::cout << res[i] << " \n"[i == q - 1];
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t = 1;
std::cin >> t;
while (t--) {
solve();
}
}