1694A - Creep
Idea: AmShZ
Solution
Tutorial is loading...
Implementation
# include <bits/stdc++.h>
using namespace std;
int t, A, B;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> t;
while (t --){
cin >> A >> B;
for (int i = 0; i < min(A, B); ++ i)
cout << "01";
for (int i = 0; i < abs(A - B); ++ i)
cout << (A < B ? 1 : 0);
cout << '\n';
}
return 0;
}
1694B - Paranoid String
Idea: AmShZ
Solution
Tutorial is loading...
Implementation
# include <bits/stdc++.h>
using namespace std;
int t, n;
string S;
long long ans;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> t;
while (t --){
cin >> n >> S, ans = n;
for (int i = 1; i < n; ++ i)
if (S[i] != S[i - 1])
ans += i;
cout << ans << '\n';
}
return 0;
}
1693A - Directional Increase
Idea: alireza_kaviani
Solution
Tutorial is loading...
Implementation
//In the name of God
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n, t, a[maxn];
long long ps[maxn];
int main(){
fast_io;
cin >> t;
while(t--){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
ps[i] = ps[i - 1] + a[i];
}
if(ps[n] != 0){
cout << "No\n";
continue;
}
bool ok = 1;
for(int i = 1; i <= n; i++){
if(ps[i] < 0) ok = 0;
}
bool visited_zero = 0;
for(int i = 1; i <= n; i++){
if(ps[i] == 0) visited_zero = 1;
else if(visited_zero) ok = 0;
}
if(ok) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
1693B - Fake Plastic Trees
Idea: AmShZ, alireza_kaviani
Solution
Tutorial is loading...
Implementation
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int t, n, l[N], r[N], ans;
vector <int> adj[N];
ll DFS(int v){
ll sum = 0;
for (int u : adj[v]){
sum += DFS(u);
}
if (sum < ll(l[v])){
++ ans;
return r[v];
}
return min(ll(r[v]), sum);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> t;
while (t --){
cin >> n;
for (int i = 2; i <= n; ++ i){
int par;
cin >> par;
adj[par].push_back(i);
}
for (int i = 1; i <= n; ++ i){
cin >> l[i] >> r[i];
}
ans = 0;
DFS(1);
cout << ans << "\n";
for (int i = 1; i <= n; ++ i){
adj[i].clear();
}
}
return 0;
}
1693C - Keshi in Search of AmShZ
Idea: AmShZ
Solution
Tutorial is loading...
Implementation
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, d[N], dist[N];
priority_queue <pair <int, int> > pq;
vector <int> adj[N];
bool mark[N];
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
fill(dist, dist + n + 1, m);
while (m --){
int v, u;
cin >> v >> u;
adj[u].push_back(v);
++ d[v];
}
dist[n] = 0;
pq.push({0, n});
while (!pq.empty()){
int v = pq.top().second;
pq.pop();
if (mark[v])
continue;
mark[v] = true;
for (int u : adj[v]){
if (dist[v] + d[u] < dist[u]){
dist[u] = dist[v] + d[u];
pq.push({- dist[u], u});
}
-- d[u];
}
}
cout << dist[1] << '\n';
return 0;
}
1693D - Decinc Dividing
Idea: AmShZ
Solution 1
Tutorial is loading...
Thanks to Koosha_Mv
Solution 2
It can be proven that a permutation is Decinc if and only if it's $$$3412$$$-avoiding and $$$2143$$$-avoiding.
Implementation 1
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a[N], dp[N], pd[N], f[N];
long long ans;
inline void upd(int i){
if (n < i)
return;
int inc = 0, dec = n + 1;
if (pd[i - 1] < a[i])
inc = max(inc, a[i - 1]);
if (a[i - 1] < a[i])
inc = max(inc, dp[i - 1]);
if (a[i] < dp[i - 1])
dec = min(dec, a[i - 1]);
if (a[i] < a[i - 1])
dec = min(dec, pd[i - 1]);
if (inc == dp[i] && dec == pd[i])
return;
dp[i] = inc, pd[i] = dec;
f[i] = 0;
if (dec <= n || inc){
upd(i + 1);
f[i] = f[i + 1] + 1;
}
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++ i)
cin >> a[i];
for (int i = n; 1 <= i; -- i){
dp[i] = n + 1;
pd[i] = 0;
upd(i + 1);
f[i] = f[i + 1] + 1;
ans += f[i];
}
cout << ans << '\n';
return 0;
}
Implementation 2
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a[N], min_r[N], fen[N];
long long ans;
stack <int> sk;
vector <int> vec[2][N];
void mofen(int pos, int val){
for (pos += 5; pos < N; pos += pos & - pos)
fen[pos] = min(fen[pos], val);
}
int gefen(int pos){
int res = n + 1;
for (pos += 5; 0 < pos; pos -= pos & - pos)
res = min(res, fen[pos]);
return res;
}
void find_3412(){
fill(fen, fen + n + 10, n + 1);
while (!sk.empty())
sk.pop();
for (int i = 1; i <= n; ++ i){
while (!sk.empty() && a[i] < a[sk.top()])
sk.pop();
if (!sk.empty())
vec[0][sk.top()].push_back(i);
sk.push(i);
}
while (!sk.empty())
sk.pop();
for (int i = n; 1 <= i; -- i){
while (!sk.empty() && a[sk.top()] < a[i])
sk.pop();
if (!sk.empty())
vec[1][sk.top()].push_back(i);
sk.push(i);
}
for (int i = n; 1 <= i; -- i){
for (int ind : vec[0][i])
mofen(a[ind], ind);
for (int ind : vec[1][i])
min_r[ind] = min(min_r[ind], gefen(a[ind] - 1));
vec[0][i].clear(), vec[1][i].clear();
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++ i)
cin >> a[i];
fill(min_r, min_r + n + 2, n + 1);
find_3412();
for (int i = 1; i <= n; ++ i)
a[i] = n + 1 - a[i];
find_3412();
for (int i = n; 1 <= i; -- i){
min_r[i] = min(min_r[i], min_r[i + 1]);
ans += min_r[i] - i;
}
cout << ans << '\n';
return 0;
}
1693E - Outermost Maximums
Idea: Keshi
Solution
Tutorial is loading...
Implementation
//In the name of God
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (lc | 1)
ll pw(ll a, ll b){
ll c = 1;
while(b){
if(b & 1) c = c * a % mod;
a = a * a % mod;
b >>= 1;
}
return c;
}
struct cost{
int c[2][2];
cost(){
memset(c, 0, sizeof c);
}
};
cost cst[2][2];
int n, a[maxn], dp[maxn], cnl[maxn], cnr[maxn];
ll s, ans, ans2;
cost seg[maxn << 2];
inline cost mrg(cost l, cost r){
cost mid;
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
mid.c[i][j] = min(r.c[i][0] + l.c[0][j], r.c[i][1] + l.c[1][j]);
}
}
return mid;
}
void bld(int id, int s, int e){
if(e - s == 1){
seg[id] = cst[int(cnl[s] > 0)][int(cnr[s] > 0)];
return;
}
int mid = (s + e) >> 1;
bld(lc, s, mid);
bld(rc, mid, e);
seg[id] = mrg(seg[lc], seg[rc]);
return;
}
void upd(int id, int s, int e, int l, int r){
if(r <= s || e <= l) return;
if(l <= s && e <= r){
seg[id] = cst[int(cnl[s] > 0)][int(cnr[s] > 0)];
return;
}
int mid = (s + e) >> 1;
upd(lc, s, mid, l, r);
upd(rc, mid, e, l, r);
seg[id] = mrg(seg[lc], seg[rc]);
return;
}
cost get(int id, int s, int e, int l, int r){
if(r <= s || e <= l) return cost();
if(l <= s && e <= r) return seg[id];
int mid = (s + e) >> 1;
return mrg(get(lc, s, mid, l, r), get(rc, mid, e, l, r));
}
int main(){
fast_io;
srand(time(NULL));
cst[0][0].c[0][0] = cst[0][0].c[1][1] = 0;
cst[0][0].c[0][1] = cst[0][0].c[1][0] = inf;
cst[0][1].c[1][0] = cst[0][1].c[1][1] = 1;
cst[0][1].c[0][0] = 0;
cst[0][1].c[0][1] = inf;
cst[1][0].c[0][1] = cst[1][0].c[0][0] = 1;
cst[1][0].c[1][1] = 0;
cst[1][0].c[1][0] = inf;
cst[1][1].c[0][0] = cst[1][1].c[1][1] = 1;
cst[1][1].c[0][1] = cst[1][1].c[1][0] = 1;
cin >> n;
cnr[0] = cnl[0] = 1;
for(int i = 1; i <= n; i++){
cin >> a[i];
cnr[a[i]]++;
s += a[i];
}
bld(1, 0, n + 1);
for(int i = 1; i <= n; i++){
cost cs = get(1, 0, n + 1, 0, a[i]);
cnr[a[i]]--;
cnl[a[i]]++;
upd(1, 0, n + 1, a[i], a[i] + 1);
dp[i] = min({cs.c[0][0], cs.c[0][1], cs.c[1][0], cs.c[1][1]});
ans += dp[i];
}
cout << ans << "\n";
return 0;
}
Check out this solution by ecnerwala
1693F - I Might Be Wrong
Idea: AmShZ
Thanks to antontrygubO_o for proof
Solution
Tutorial is loading...
Implementation by Um_nik
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#ifdef LOCAL
#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const int N = 200200;
int n;
char s[N];
int bal[N];
int pos[N];
void solve() {
scanf("%d %s", &n, s);
int b = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0')
b++;
else
b--;
}
if (b < 0) {
for (int i = 0; i < n; i++)
s[i] ^= 1;
reverse(s, s + n);
b *= -1;
}
bal[0] = (n + b) / 2;
for (int i = 0; i < n; i++)
bal[i + 1] = bal[i] + (s[i] == '0' ? -1 : 1);
assert(bal[n] == (n - b) / 2);
for (int i = 0; i <= n; i++)
pos[i] = -1;
for (int i = 0; i <= n; i++)
pos[bal[i]] = i;
int ans = 0;
int l = 0;
while(l < (n + b) / 2) {
if (bal[l + 1] < bal[l]) {
l++;
continue;
}
if (bal[l] <= (n - b) / 2) {
ans++;
break;
}
int r = pos[bal[l]];
assert(r > l);
ans++;
for (int i = l + 1; i < r; i++) {
if (2 * i > l + r) {
bal[i] = bal[l] - (r - i);
} else {
bal[i] = bal[l] - (i - l);
}
pos[bal[i]] = max(pos[bal[i]], i);
}
}
printf("%d\n", ans);
}
int main()
{
startTime = clock();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int t;
scanf("%d", &t);
while(t--) solve();
return 0;
}
Thanks to Um_nik