Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
n = int(input())
a = list(map(int, input().split()))
l, r = a.index(1), n - a[::-1].index(1) - 1
c = a.count(1)
print(r - l - c + 1)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n), x(n);
for (auto& it : a) cin >> it;
for (auto& it : x) cin >> it;
vector<long long> s(n + 1);
for (int i = 0; i < n; ++i) s[abs(x[i])] += a[i];
bool ok = true;
long long lft = 0;
for (int i = 1; i <= n; ++i) {
lft += k - s[i];
ok &= (lft >= 0);
}
cout << (ok ? "YES" : "NO") << '\n';
}
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = 300043;
int t;
int n, m;
int a[N];
long long sum[N];
int cnt1[N];
int main() {
ios_base::sync_with_stdio(false);
cin >> t;
for (int tc = 0; tc < t; ++tc) {
cin >> n >> m;
memset(sum, 0, sizeof(sum[0]) * (n + 5));
memset(cnt1, 0, sizeof(cnt1[0]) * (n + 5));
for (int i = 0; i < n; ++i) {
cin >> a[i];
sum[i + 1] = sum[i] + a[i];
cnt1[i + 1] = cnt1[i] + (a[i] == 1);
}
for (int i = 0; i < m; ++i) {
int l, r;
cin >> l >> r;
--l;
int cur_cnt1 = cnt1[r] - cnt1[l];
long long cur_sum = sum[r] - sum[l];
if((r - l) + cur_cnt1 <= cur_sum && r - l > 1)
cout << "YES\n";
else
cout << "NO\n";
}
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x;
vector<int> ans(n, n);
for (int z = 0; z < 2; ++z) {
vector<long long> s(n + 1);
for (int i = 0; i < n; ++i) s[i + 1] = s[i] + a[i];
vector<int> p(n, -1);
for (int i = 1; i < n; ++i) {
int j = (z ? n - i - 1 : i);
int l = 1, r = i;
while (l <= r) {
int m = (l + r) / 2;
if (s[i] - s[i - m] > a[i] && p[i - 1] >= i - m) {
ans[j] = min(ans[j], m);
r = m - 1;
} else {
l = m + 1;
}
}
if (a[i - 1] > a[i]) ans[j] = 1;
p[i] = (a[i] == a[i - 1] ? p[i - 1] : i - 1);
}
reverse(a.begin(), a.end());
}
for (int i = 0; i < n; ++i)
cout << (ans[i] == n ? -1 : ans[i]) << ' ';
cout << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int n;
vector<int> a;
vector<vector<int>> g;
long long ans;
vector<map<int, int>> cnt;
void dfs(int v, int p = -1){
int bst = -1;
for (int u : g[v]) if (u != p){
dfs(u, v);
if (bst == -1 || cnt[bst].size() < cnt[u].size())
bst = u;
}
for (int u : g[v]) if (u != p && u != bst){
for (auto it : cnt[u]){
int x = it.first, y = it.second;
if (x != a[v]) ans += cnt[bst][x] * 1ll * y;
cnt[bst][x] += y;
}
}
if (bst != -1) swap(cnt[bst], cnt[v]);
ans += cnt[v][a[v]];
cnt[v][a[v]] = 1;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--){
int n;
cin >> n;
a.resize(n);
forn(i, n) cin >> a[i];
g.assign(n, {});
forn(_, n - 1){
int v, u;
cin >> v >> u;
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
ans = 0;
cnt.assign(n, {});
dfs(0);
cout << ans << '\n';
}
return 0;
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
typedef long long li;
typedef pair<int, int> pt;
const int INF = int(1e9);
const int MOD = int(1e9) + 7;
int add(int a, int b) {
a += b;
if (a >= MOD)
a -= MOD;
return a;
}
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
namespace SuffixArray {
string s;
vector< array<int, 2> > classes;
vector<int> build(const string &bs) {
s = bs;
s += '$';
vector<int> c(all(s)), ord(sz(s));
iota(all(ord), 0);
classes.resize(sz(s));
for (int len = 1; len < 2 * sz(s); len <<= 1) {
int half = len >> 1;
fore (i, 0, sz(s))
classes[i] = {c[i], c[(i + half) % sz(s)]};
sort(all(ord), [&](int i, int j) {
return classes[i] < classes[j];
});
c[ord[0]] = 0;
fore (i, 1, sz(ord))
c[ord[i]] = c[ord[i - 1]] + (classes[ord[i - 1]] != classes[ord[i]]);
}
c.pop_back();
for (int &cc : c)
cc--;
return c;
}
};
int n, k;
string s;
inline bool read() {
if(!(cin >> n >> k))
return false;
cin >> s;
return true;
}
string calcZero(string s) {
int rem = k;
int pos = 0;
for (int i = sz(s) - 1; rem > 0 && i >= 0; i--) {
if (s[i] == '1')
continue;
while (pos < sz(s) && s[pos] == '0')
pos++;
if (pos >= i)
break;
swap(s[pos], s[i]);
rem--;
}
return s.substr(s.find('1'));
}
string calcOne(string s) {
reverse(all(s));
auto c = SuffixArray::build(s);
int cntOnes = count(all(s), '1');
array<int, 3> mn = { 2 * sz(s), INF, -1 };
int u = 0, curOnes = 0;
fore (i, 0, n) {
while (u < sz(s) && (u - i < cntOnes || cntOnes - curOnes > k - 1)) {
curOnes += s[u] == '1';
u++;
}
if (u - i < cntOnes || cntOnes - curOnes > k - 1)
break;
array<int, 3> curAns = { u - i, c[i], i };
mn = min(mn, curAns);
curOnes -= s[i] == '1';
}
assert(mn[2] >= 0);
string res = s.substr(mn[2], mn[0]);
int toAdd = cntOnes - count(all(res), '1');
for (int i = sz(res) - 1; toAdd > 0 && i >= 0; i--) {
if (res[i] == '0') {
res[i] = '1';
toAdd--;
}
}
return res;
}
inline void solve() {
auto s1 = calcZero(s);
auto s2 = calcOne(s);
if (sz(s1) > sz(s2) || (sz(s1) == sz(s2) && s1 > s2))
swap(s1, s2);
int res = 0;
for (char c : s1)
res = add(mul(res, 2), c - '0');
cout << res << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}