[problem:2244A]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2244A]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using ll = long long;↵
using namespace std;↵
↵
void I_love_feblokas();↵
↵
int32_t main() {↵
int32_t tc = 1;↵
cin >> tc;↵
while (tc-->0) {↵
I_love_feblokas();↵
}↵
return 0;↵
}↵
↵
void I_love_feblokas() {↵
int32_t ans = 0, cnt = 0;↵
int n;↵
cin >> n;↵
string s;↵
cin >> s;↵
for (auto &c : s) {↵
if (c == '*') {↵
cnt = 0;↵
} else {↵
cnt++;↵
}↵
ans = max(ans, (cnt + 1) / 2);↵
}↵
cout << ans << '\n';↵
return;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2244B]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2244B]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using ll = long long;↵
using namespace std;↵
↵
void I_love_feblokas();↵
↵
int32_t main() {↵
int32_t tc = 1;↵
cin >> tc;↵
while (tc-- > 0) {↵
I_love_feblokas();↵
}↵
return 0;↵
}↵
↵
void I_love_feblokas() {↵
int n;↵
cin >> n;↵
vector<ll> a(n);↵
for (auto &x : a) cin >> x;↵
ll cur = 0;↵
bool ok = true;↵
for (ll i = 0; i < n; ++i) {↵
cur += a[i];↵
ll need = (i + 1) * (i + 2) / 2;↵
if (cur < need) {↵
ok = false;↵
}↵
}↵
if (ok) {↵
cout << "YES\n";↵
} else {↵
cout << "NO\n";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2244C]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2244C]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using ll = long long;↵
using namespace std;↵
↵
void I_love_feblokas();↵
↵
int32_t main() {↵
int32_t tc = 1;↵
cin >> tc;↵
while (tc-- > 0) {↵
I_love_feblokas();↵
}↵
return 0;↵
}↵
↵
void I_love_feblokas() {↵
int n, x, y;↵
cin >> n >> x >> y;↵
vector<int> p(n);↵
for (auto &val : p) cin >> val;↵
↵
int g = gcd(x, y);↵
bool ok = true;↵
↵
for (int i = 0; i < n; ++i) {↵
if ((p[i] % g) != ((i + 1) % g)) {↵
ok = false;↵
break;↵
}↵
}↵
↵
if (ok) {↵
cout << "YES\n";↵
} else {↵
cout << "NO\n";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2244D]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2244D]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using ll = long long;↵
using namespace std;↵
↵
void I_love_feblokas();↵
↵
int32_t main() {↵
int32_t tc = 1;↵
cin >> tc;↵
while (tc-->0) {↵
I_love_feblokas();↵
}↵
return 0;↵
}↵
↵
void I_love_feblokas() {↵
int n, m;↵
ll ans = 0;↵
cin >> n >> m;↵
vector<ll> a(n), b(m);↵
for (auto &x : a) cin >> x;↵
for (auto &x : b) cin >> x;↵
b.push_back(0);↵
sort(b.begin(), b.end());↵
vector<ll> pref(n + 1);↵
for (ll i = 0; i < n; ++i) {↵
pref[i + 1] = pref[i] + a[i];↵
}↵
for (ll i = 1; i < b.size(); ++i) {↵
ans += abs(pref[b[i]] - pref[b[i - 1]]);↵
}↵
ans += pref[n] - pref[b.back()];↵
cout << ans << '\n';↵
return;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
[problem:2244E]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2244E]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
void solve() {↵
int n, q;↵
cin >> n >> q;↵
string s;↵
cin >> s;↵
vector<int> pref(n, 0);↵
for (int i = 0; i < n — 1; ++i) {↵
pref[i + 1] = pref[i] + (s[i] == s[i + 1] ? 1 : 0);↵
}↵
for (int i = 0; i < q; ++i) {↵
int l, r, k;↵
cin >> l >> r >> k;↵
if (l == r) {↵
cout << "YES\n";↵
continue;↵
}↵
int c = pref[r — 1] — pref[l — 1];↵
int needed = (c + 1) / 2;↵
if (needed <= k) cout << "YES\n";↵
else cout << "NO\n";↵
}↵
}↵
↵
int main() {↵
int t;↵
cin >> t;↵
while (t--) solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2244F]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2244F]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using ll = long long;↵
using namespace std;↵
↵
vector<vector<int>> g;↵
vector<int> leaf;↵
bool ok;↵
↵
void I_love_feblokas();↵
pair<int, int> dfs(int u, int p);↵
↵
int32_t main() {↵
int32_t tc = 1;↵
cin >> tc;↵
while (tc-- > 0) {↵
I_love_feblokas();↵
}↵
return 0;↵
}↵
↵
pair<int, int> dfs(int u, int p) {↵
if (!ok) return {0, 0};↵
if (leaf[u] != 0) {↵
for (int v : g[u]) {↵
if (v != p) {↵
ok = false;↵
return {0, 0};↵
}↵
}↵
return {leaf[u], leaf[u]};↵
}↵
vector<pair<int, int>> segs;↵
for (int v : g[u]) {↵
if (v != p) {↵
segs.push_back(dfs(v, u));↵
if (!ok) return {0, 0};↵
}↵
}↵
if (segs.empty()) {↵
ok = false;↵
return {0, 0};↵
}↵
vector<pair<int, int>> sorted_segs = segs;↵
sort(sorted_segs.begin(), sorted_segs.end());↵
for (size_t i = 0; i < sorted_segs.size() — 1; ++i) {↵
if (sorted_segs[i].second + 1 != sorted_segs[i + 1].first) {↵
ok = false;↵
return {0, 0};↵
}↵
}↵
int start_pos = -1;↵
for (size_t i = 0; i < segs.size(); ++i) {↵
if (segs[i] == sorted_segs[0]) {↵
start_pos = i;↵
break;↵
}↵
}↵
if (start_pos == -1) {↵
ok = false;↵
return {0, 0};↵
}↵
for (size_t i = 0; i < segs.size(); ++i) {↵
if (segs[(start_pos + i) % segs.size()] != sorted_segs[i]) {↵
ok = false;↵
return {0, 0};↵
}↵
}↵
return {sorted_segs[0].first, sorted_segs.back().second};↵
}↵
↵
void I_love_feblokas() {↵
int n;↵
cin >> n;↵
g.assign(n + 1, vector<int>());↵
leaf.assign(n + 1, 0);↵
ok = true;↵
for (int i = 2; i <= n; ++i) {↵
int p;↵
cin >> p;↵
g[p].push_back(i);↵
g[i].push_back(p);↵
}↵
int k = 0;↵
for (int i = 1; i <= n; ++i) {↵
cin >> leaf[i];↵
k = max(k, leaf[i]);↵
}↵
if (n == 1) {↵
cout << "YES\n";↵
return;↵
}↵
pair<int, int> res = dfs(1, -1);↵
if (ok && res.first == 1 && res.second == k) {↵
cout << "YES\n";↵
} else {↵
cout << "NO\n";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2244G]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2244G]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
struct Fenwick {↵
int n;↵
vector<ll> t;↵
↵
Fenwick(int n) : n(n), t(n + 1, 0ll) {}↵
↵
int f(int x) {↵
return x & -x;↵
}↵
↵
void upd(int pos, ll val) {↵
for (; pos <= n; pos += f(pos)) t[pos] = max(t[pos], val);↵
}↵
↵
ll get(int pos) {↵
ll ans = 0;↵
for (; pos > 0; pos -= f(pos)) ans = max(ans, t[pos]);↵
return ans;↵
}↵
};↵
↵
void I_love_feblokas() {↵
int n;↵
cin >> n;↵
vector<ll> a(n + 1);↵
for (int i = 1; i <= n; ++i) {↵
cin >> a[i];↵
}↵
Fenwick t(n);↵
vector<vector<pair<int, ll>>> ev(n + 1);↵
ll ans = 0;↵
for (int i = 1; i <= n; ++i) {↵
for (auto& ev : ev[i]) {↵
t.upd(ev.first, ev.second);↵
}↵
int lim = i— a[i] —- a[i] - 1;↵
ll mx = 0;↵
if (lim > 0) {↵
mx = t.get(min(n, lim));↵
}↵
ll dp_i = a[i] + mx;↵
ans = max(ans, dp_i);↵
ll act = i + a[i] + 1;↵
if (act <= n) {↵
ev[act].push_back({i, dp_i});↵
}↵
}↵
cout << ans << "\n";↵
}↵
↵
int main() {↵
int t;↵
cin >> t ;↵
while (t--) {↵
I_love_feblokas();↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2244A]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using ll = long long;↵
using namespace std;↵
↵
void I_love_feblokas();↵
↵
int32_t main() {↵
int32_t tc = 1;↵
cin >> tc;↵
while (tc-->0) {↵
I_love_feblokas();↵
}↵
return 0;↵
}↵
↵
void I_love_feblokas() {↵
int32_t ans = 0, cnt = 0;↵
int n;↵
cin >> n;↵
string s;↵
cin >> s;↵
for (auto &c : s) {↵
if (c == '*') {↵
cnt = 0;↵
} else {↵
cnt++;↵
}↵
ans = max(ans, (cnt + 1) / 2);↵
}↵
cout << ans << '\n';↵
return;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2244B]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2244B]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using ll = long long;↵
using namespace std;↵
↵
void I_love_feblokas();↵
↵
int32_t main() {↵
int32_t tc = 1;↵
cin >> tc;↵
while (tc-- > 0) {↵
I_love_feblokas();↵
}↵
return 0;↵
}↵
↵
void I_love_feblokas() {↵
int n;↵
cin >> n;↵
vector<ll> a(n);↵
for (auto &x : a) cin >> x;↵
ll cur = 0;↵
bool ok = true;↵
for (ll i = 0; i < n; ++i) {↵
cur += a[i];↵
ll need = (i + 1) * (i + 2) / 2;↵
if (cur < need) {↵
ok = false;↵
}↵
}↵
if (ok) {↵
cout << "YES\n";↵
} else {↵
cout << "NO\n";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2244C]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2244C]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using ll = long long;↵
using namespace std;↵
↵
void I_love_feblokas();↵
↵
int32_t main() {↵
int32_t tc = 1;↵
cin >> tc;↵
while (tc-- > 0) {↵
I_love_feblokas();↵
}↵
return 0;↵
}↵
↵
void I_love_feblokas() {↵
int n, x, y;↵
cin >> n >> x >> y;↵
vector<int> p(n);↵
for (auto &val : p) cin >> val;↵
↵
int g = gcd(x, y);↵
bool ok = true;↵
↵
for (int i = 0; i < n; ++i) {↵
if ((p[i] % g) != ((i + 1) % g)) {↵
ok = false;↵
break;↵
}↵
}↵
↵
if (ok) {↵
cout << "YES\n";↵
} else {↵
cout << "NO\n";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2244D]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2244D]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using ll = long long;↵
using namespace std;↵
↵
void I_love_feblokas();↵
↵
int32_t main() {↵
int32_t tc = 1;↵
cin >> tc;↵
while (tc-->0) {↵
I_love_feblokas();↵
}↵
return 0;↵
}↵
↵
void I_love_feblokas() {↵
int n, m;↵
ll ans = 0;↵
cin >> n >> m;↵
vector<ll> a(n), b(m);↵
for (auto &x : a) cin >> x;↵
for (auto &x : b) cin >> x;↵
b.push_back(0);↵
sort(b.begin(), b.end());↵
vector<ll> pref(n + 1);↵
for (ll i = 0; i < n; ++i) {↵
pref[i + 1] = pref[i] + a[i];↵
}↵
for (ll i = 1; i < b.size(); ++i) {↵
ans += abs(pref[b[i]] - pref[b[i - 1]]);↵
}↵
ans += pref[n] - pref[b.back()];↵
cout << ans << '\n';↵
return;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
[problem:2244E]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2244E]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
void solve() {↵
int n, q;↵
cin >> n >> q;↵
string s;↵
cin >> s;↵
vector<int> pref(n, 0);↵
for (int i = 0; i < n — 1; ++i) {↵
pref[i + 1] = pref[i] + (s[i] == s[i + 1] ? 1 : 0);↵
}↵
for (int i = 0; i < q; ++i) {↵
int l, r, k;↵
cin >> l >> r >> k;↵
if (l == r) {↵
cout << "YES\n";↵
continue;↵
}↵
int c = pref[r — 1] — pref[l — 1];↵
int needed = (c + 1) / 2;↵
if (needed <= k) cout << "YES\n";↵
else cout << "NO\n";↵
}↵
}↵
↵
int main() {↵
int t;↵
cin >> t;↵
while (t--) solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2244F]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2244F]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using ll = long long;↵
using namespace std;↵
↵
vector<vector<int>> g;↵
vector<int> leaf;↵
bool ok;↵
↵
void I_love_feblokas();↵
pair<int, int> dfs(int u, int p);↵
↵
int32_t main() {↵
int32_t tc = 1;↵
cin >> tc;↵
while (tc-- > 0) {↵
I_love_feblokas();↵
}↵
return 0;↵
}↵
↵
pair<int, int> dfs(int u, int p) {↵
if (!ok) return {0, 0};↵
if (leaf[u] != 0) {↵
for (int v : g[u]) {↵
if (v != p) {↵
ok = false;↵
return {0, 0};↵
}↵
}↵
return {leaf[u], leaf[u]};↵
}↵
vector<pair<int, int>> segs;↵
for (int v : g[u]) {↵
if (v != p) {↵
segs.push_back(dfs(v, u));↵
if (!ok) return {0, 0};↵
}↵
}↵
if (segs.empty()) {↵
ok = false;↵
return {0, 0};↵
}↵
vector<pair<int, int>> sorted_segs = segs;↵
sort(sorted_segs.begin(), sorted_segs.end());↵
for (size_t i = 0; i < sorted_segs.size() — 1; ++i) {↵
if (sorted_segs[i].second + 1 != sorted_segs[i + 1].first) {↵
ok = false;↵
return {0, 0};↵
}↵
}↵
int start_pos = -1;↵
for (size_t i = 0; i < segs.size(); ++i) {↵
if (segs[i] == sorted_segs[0]) {↵
start_pos = i;↵
break;↵
}↵
}↵
if (start_pos == -1) {↵
ok = false;↵
return {0, 0};↵
}↵
for (size_t i = 0; i < segs.size(); ++i) {↵
if (segs[(start_pos + i) % segs.size()] != sorted_segs[i]) {↵
ok = false;↵
return {0, 0};↵
}↵
}↵
return {sorted_segs[0].first, sorted_segs.back().second};↵
}↵
↵
void I_love_feblokas() {↵
int n;↵
cin >> n;↵
g.assign(n + 1, vector<int>());↵
leaf.assign(n + 1, 0);↵
ok = true;↵
for (int i = 2; i <= n; ++i) {↵
int p;↵
cin >> p;↵
g[p].push_back(i);↵
g[i].push_back(p);↵
}↵
int k = 0;↵
for (int i = 1; i <= n; ++i) {↵
cin >> leaf[i];↵
k = max(k, leaf[i]);↵
}↵
if (n == 1) {↵
cout << "YES\n";↵
return;↵
}↵
pair<int, int> res = dfs(1, -1);↵
if (ok && res.first == 1 && res.second == k) {↵
cout << "YES\n";↵
} else {↵
cout << "NO\n";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2244G]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2244G]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
struct Fenwick {↵
int n;↵
vector<ll> t;↵
↵
Fenwick(int n) : n(n), t(n + 1, 0ll) {}↵
↵
int f(int x) {↵
return x & -x;↵
}↵
↵
void upd(int pos, ll val) {↵
for (; pos <= n; pos += f(pos)) t[pos] = max(t[pos], val);↵
}↵
↵
ll get(int pos) {↵
ll ans = 0;↵
for (; pos > 0; pos -= f(pos)) ans = max(ans, t[pos]);↵
return ans;↵
}↵
};↵
↵
void I_love_feblokas() {↵
int n;↵
cin >> n;↵
vector<ll> a(n + 1);↵
for (int i = 1; i <= n; ++i) {↵
cin >> a[i];↵
}↵
Fenwick t(n);↵
vector<vector<pair<int, ll>>> ev(n + 1);↵
ll ans = 0;↵
for (int i = 1; i <= n; ++i) {↵
for (auto& ev : ev[i]) {↵
t.upd(ev.first, ev.second);↵
}↵
int lim = i
ll mx = 0;↵
if (lim > 0) {↵
mx = t.get(min(n, lim));↵
}↵
ll dp_i = a[i] + mx;↵
ans = max(ans, dp_i);↵
ll act = i + a[i] + 1;↵
if (act <= n) {↵
ev[act].push_back({i, dp_i});↵
}↵
}↵
cout << ans << "\n";↵
}↵
↵
int main() {↵
int t;↵
cin >> t ;↵
while (t--) {↵
I_love_feblokas();↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
