1002. B. Binary Choice
cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 200010;
int a[N], b[N], c[N];
int head[N * 2], ver[N * 2], ne[N * 2], tot = 1;
int mark[N * 2], res1[N * 2], res2[N * 2], vis[N * 2];
int f[N * 2];
vector<int> values;
void add(int x, int y) {
ver[++tot] = y;
ne[tot] = head[x];
head[x] = tot;
}
bool dfs(int x) {
if (vis[x]) return false;
vis[x] = true;
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (dfs(y)) mark[i / 2] = true;
}
return true;
}
bool dfs2(int x) {
if (vis[x]) return false;
vis[x] = true;
// cout << "awa" << x << '\n';
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (dfs2(y)) {
if (f[y] & 1) {
f[y]++;
if (i % 2 == 0) res1[i / 2] = 1;
}
else {
f[x]++;
if (i & 1) res1[i / 2] = 1;
}
}
}
return true;
}
void dfs3(int x, int col) {
if (res2[x] != -1) return;
res2[x] = col;
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
dfs3(y, col ^ 1);
}
}
void solve() {
int n;
cin >> n;
values.clear();
for (int i = 1; i <= n; ++i) {
cin >> a[i] >> b[i] >> c[i];
values.emplace_back(a[i]), values.emplace_back(b[i]);
}
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
int m = values.size();
fill(head, head + m + 1, 0);
tot = 1;
// cout << "building edges 1" << endl;
for (int i = 1; i <= n; ++i) {
a[i] = lower_bound(values.begin(), values.end(), a[i]) - values.begin() + 1;
b[i] = lower_bound(values.begin(), values.end(), b[i]) - values.begin() + 1;
// cout << a[i] << ' ' << b[i] << endl;
add(a[i], b[i]), add(b[i], a[i]);
}
fill(vis, vis + m + 1, 0);
fill(f, f + m + 1, 0);
fill(mark, mark + n + 1, 0);
for (int i = 1; i <= m; ++i) {
if (!vis[i]) dfs(i);
}
for (int i = 1; i <= n; ++i) {
if (!mark[i]) f[ver[i * 2 + 1]]++;
}
fill(vis, vis + m + 1, 0);
fill(res1, res1 + n + 1, 0);
for (int i = 1; i <= m; ++i) {
if (!vis[i]) {
dfs2(i);
if (f[i] & 1) {
cout << -1 << '\n';
return;
}
}
}
tot = 1;
fill(head, head + n + 1, 0);
fill(f, f + m + 1, 0);
values.clear();
for (int i = 1; i <= n; ++i) {
int cur = res1[i] ? b[i] : a[i];
if (f[cur]) add(i, f[cur]), add(f[cur], i), f[cur] = 0;
else f[cur] = i;
values.emplace_back(c[i]);
}
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
m = values.size();
fill(f, f + m + 1, 0);
for (int i = 1; i <= n; ++i) {
c[i] = lower_bound(values.begin(), values.end(), c[i]) - values.begin() + 1;
}
for (int i = 1; i <= n; ++i) {
int cur = c[i];
if (f[cur]) add(i, f[cur]), add(f[cur], i), f[cur] = 0;
else f[cur] = i;
}
fill(res2, res2 + n + 1, -1);
for (int i = 1; i <= n; ++i) {
if (res2[i] == -1) {
dfs3(i, 0);
}
}
for (int i = 1; i <= n; ++i) cout << res1[i];
cout << '\n';
for (int i = 1; i <= n; ++i) cout << res2[i];
cout << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}1003. C. Stalin Sort
cpp
#include <iostream>
using namespace std;
const int N = 200010;
int tr0[N * 4]; // max
int tr2[N * 4]; // min
int tr1[N], n; // count
int a[N];
void modify0(int u, int l, int r, int p, int v) {
if (l == r) tr0[u] = v;
else {
int mid = l + r >> 1;
if (p <= mid) modify0(u << 1, l, mid, p, v);
else modify0(u << 1 | 1, mid + 1, r, p, v);
tr0[u] = max(tr0[u << 1], tr0[u << 1 | 1]);
}
}
int query0(int u, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tr0[u];
else {
int mid = l + r >> 1, res = 0;
if (ql <= mid) res = query0(u << 1, l, mid, ql, qr);
if (qr > mid) res = max(res, query0(u << 1 | 1, mid + 1, r, ql, qr));
return res;
}
}
void modify2(int u, int l, int r, int p, int v) {
if (l == r) tr2[u] = v;
else {
int mid = l + r >> 1;
if (p <= mid) modify2(u << 1, l, mid, p, v);
else modify2(u << 1 | 1, mid + 1, r, p, v);
tr2[u] = min(tr2[u << 1], tr2[u << 1 | 1]);
}
}
int query2(int u, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tr2[u];
else {
int mid = l + r >> 1, res = n + 1;
if (ql <= mid) res = query2(u << 1, l, mid, ql, qr);
if (qr > mid) res = min(res, query2(u << 1 | 1, mid + 1, r, ql, qr));
return res;
}
}
void add1(int x, int v) {
for (; x <= n; x += x & -x) {
tr1[x] += v;
}
}
int query(int x) {
int res = 0;
for (; x; x -= x & -x) {
res += tr1[x];
}
return res;
}
int query1(int l, int r) {
if (l > r) return 0;
else return query(r) - query(l - 1);
}
void print(int *tr, int u, int l, int r) {
if (l == r) cout << tr[u] << ' ';
else {
int mid = l + r >> 1;
print(tr, u << 1, l, mid), print(tr, u << 1 | 1, mid + 1, r);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int q;
cin >> n >> q;
fill(tr0, tr0 + n * 4, 0);
fill(tr1, tr1 + n + 1, 0);
fill(tr2, tr2 + n * 4, n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (a[i] == 0) modify0(1, 1, n, i, i);
else if (a[i] == 2) modify2(1, 1, n, i, i);
else add1(i, 1);
// print(tr0, 1, 1, n);
// cout << '\n';
// print(tr2, 1, 1, n);
// cout << "\n\n";
}
while (q--) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
if (a[x] == y) continue;
if (a[x] == 0) modify0(1, 1, n, x, 0);
else if (a[x] == 2) modify2(1, 1, n, x, n + 1);
else add1(x, -1);
if (y == 0) modify0(1, 1, n, x, x);
else if (y == 2) modify2(1, 1, n, x, x);
else add1(x, 1);
a[x] = y;
}
else {
int p0 = query0(1, 1, n, x, y); // r0 0
int p2 = query2(1, 1, n, x, y); // l2 inf
// cout << p0 << ' ' << p2 << '\n';
if (p0 < p2 && query1(x, p0) == 0 && query1(p2, y) == 0) cout << 0 << '\n';
else if (query1(p2, p0)) cout << 2 << '\n';
else cout << 1 << '\n';
}
}
}
return 0;
}1005. E. TREE
cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 1e9 + 7;
const int INF = 1e18;
struct Seg {
int n;
vi tr;
Seg(int n) : n(n), tr(n * 4 + 4, -INF) {}
void set(int u, int l, int r, int p, int x) {
if (l == r) {
tr[u] = x;
return;
}
int m = (l + r) >> 1;
if (p <= m)
set(u << 1, l, m, p, x);
else
set(u << 1 | 1, m + 1, r, p, x);
tr[u] = max(tr[u << 1], tr[u << 1 | 1]);
}
int qry(int u, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr)
return tr[u];
int m = (l + r) >> 1;
int res = -INF;
if (ql <= m)
res = max(res, qry(u << 1, l, m, ql, qr));
if (qr > m)
res = max(res, qry(u << 1 | 1, m + 1, r, ql, qr));
return res;
}
void set(int p, int x) {
set(1, 1, n, p, x);
}
int qry(int l, int r) {
if (l > r)
return -INF;
return qry(1, 1, n, l, r);
}
};
void calc(const vi &a, const vector<vpii> &qs, vi &ans) {
int n = sz(a) - 1;
Seg seg(n);
vi st;
vi dep(n + 1);
vi val(n + 1);
for (int i = 1; i <= n; i++) {
int mx = -INF;
while (!st.empty() && a[st.back()] > a[i]) {
int u = st.back();
st.pop_back();
mx = max(mx, val[u]);
seg.set(u, -INF);
}
dep[i] = sz(st) + 1;
if (mx == -INF)
val[i] = dep[i];
else
val[i] = mx + 1;
st.pb(i);
seg.set(i, val[i]);
for (auto [x, id] : qs[i]) {
int res = 1;
if (x < i) {
int v = seg.qry(x + 1, i);
res = max(res, v - dep[x] + 1);
}
ans[id] = res;
}
}
}
void solve() {
int n, q;
cin >> n >> q;
vi a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
vi lc(n + 1);
vi rc(n + 1);
vi fa(n + 1);
vi st;
for (int i = 1; i <= n; i++) {
int las = 0;
while (!st.empty() && a[st.back()] > a[i]) {
las = st.back();
st.pop_back();
}
if (!st.empty()) {
rc[st.back()] = i;
fa[i] = st.back();
}
if (las) {
lc[i] = las;
fa[las] = i;
}
st.pb(i);
}
int rt = st[0];
int lg = 1;
while ((1LL << lg) <= n)
lg++;
vvi up(lg, vi(n + 1));
vi dep(n + 1);
dep[rt] = 1;
vi ord = {rt};
for (int i = 0; i < sz(ord); i++) {
int u = ord[i];
if (lc[u]) {
int v = lc[u];
up[0][v] = u;
dep[v] = dep[u] + 1;
ord.pb(v);
}
if (rc[u]) {
int v = rc[u];
up[0][v] = u;
dep[v] = dep[u] + 1;
ord.pb(v);
}
}
for (int j = 1; j < lg; j++) {
for (int i = 1; i <= n; i++) {
up[j][i] = up[j - 1][up[j - 1][i]];
}
}
auto lca = [&](int x, int y) {
if (dep[x] < dep[y])
swap(x, y);
int d = dep[x] - dep[y];
for (int j = 0; j < lg; j++) {
if (d >> j & 1)
x = up[j][x];
}
if (x == y)
return x;
for (int j = lg - 1; j >= 0; j--) {
if (up[j][x] != up[j][y]) {
x = up[j][x];
y = up[j][y];
}
}
return up[0][x];
};
vector<vpii> qr(n + 1);
vector<vpii> ql(n + 1);
for (int id = 0; id < q; id++) {
int l, r;
cin >> l >> r;
int p = lca(l, r);
qr[r].pb({p, id});
int nl = n - p + 1;
int nr = n - l + 1;
ql[nr].pb({nl, id});
}
vi ar(n + 1);
for (int i = 1; i <= n; i++)
ar[i] = a[n - i + 1];
vi R(q);
vi L(q);
calc(a, qr, R);
calc(ar, ql, L);
for (int i = 0; i < q; i++) {
cout << max(L[i], R[i]) << endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}1006. F. Median Shuffle
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';
void solve() {
int n;
cin >> n;
int t = (n * 3 + 1) / 2;
vector<int> cnt(n + 1);
for (int i = 1; i <= t; i ++) {
int x;
cin >> x;
cnt[x] ++;
}
vector<int> b;
for (int i = 1; i <= n; i ++) {
if (cnt[i] == 0) {
cout << -1 << '\n';
return;
}
while (cnt[i] > 1) {
b.push_back(i);
cnt[i] --;
}
}
sort(b.begin(), b.end(), [&](int x, int y) {
int dis1 = min(x - 1, n - x);
int dis2 = min(y - 1, n - y);
return dis1 < dis2;
});
for (int i = 0; i < size(b); i ++) {
if (min(b[i] - 1, n - b[i]) < i) {
cout << "-1\n";
return;
}
}
int pos_l = 1, pos_r = n;
vector<int> vis(n + 1);
vector<int> ans;
auto get_l = [&]() {
while (pos_l <= n && vis[pos_l]) pos_l ++;
if (pos_l > n) return -1;
int x = pos_l ++;
vis[x] = 1;
return x;
};
auto get_r = [&]() {
while (pos_r >= 1 && vis[pos_r]) pos_r --;
if (pos_r < 1) return -1;
int x = pos_r --;
vis[x] = 1;
return x;
};
int mid = 0;
for (auto x : b) {
if (mid == 0) {
vis[x] = 1;
ans.push_back(x);
mid = x;
continue;
}
if (x == mid) {
int u = get_l(), v = get_r();
if (u == -1 || v == -1) {
cout << "-1\n";
return;
}
ans.push_back(u);
ans.push_back(v);
} else if (x < mid) {
if (vis[x]) {
int u = get_l(), v = get_l();
if (u == -1 || v == -1) {
cout << -1 << '\n';
return;
}
ans.push_back(u);
ans.push_back(v);
} else {
vis[x] = 1;
int u = get_l();
if (u == -1) {
cout << -1 << '\n';
return;
}
ans.push_back(u);
ans.push_back(x);
}
} else {
if (vis[x]) {
int u = get_r(), v = get_r();
if (u == -1 || v == -1) {
cout << -1 << '\n';
return;
}
ans.push_back(u);
ans.push_back(v);
} else {
vis[x] = 1;
int u = get_r();
if (u == -1) {
cout << -1 << '\n';
return;
}
ans.push_back(x);
ans.push_back(u);
}
}
mid = x;
}
for (int x : ans) cout << x << ' ';
cout << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("in.txt", "r", stdin);
int t;
cin >> t;
while (t --) solve();
}1007. G. Perfect Palindrome
cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int f[N][26];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, d;
string s;
cin >> n >> d >> s;
int len = __gcd(n, d);
if (n / len % 2 == 0) {
fill(f[0], f[0] + 26 * len, 0);
bool flag = 0;
for (int i = 1; i <= n; i += len) {
for (int j = 0; j < len; ++j) {
int idx = flag ? j : len - j - 1;
f[idx][s[i + j - 1] - 'a']++;
}
flag ^= 1;
}
int res = 0;
for (int i = 0; i < len; ++i) {
int mx = 0;
for (int j = 0; j < 26; ++j) {
res += f[i][j];
mx = max(mx, f[i][j]);
}
res -= mx;
}
cout << res << '\n';
}
else {
fill(f[0], f[0] + 26 * (len + 1) / 2, 0);
for (int i = 1; i <= n; i += len) {
for (int j = 0; j < len / 2; ++j) {
f[j][s[i + j - 1] - 'a']++;
f[j][s[i + len - j - 2] - 'a']++;
}
if (len & 1) f[len / 2][s[i + len / 2 - 1] - 'a']++;
}
int res = 0;
for (int i = 0; i < (len + 1) / 2; ++i) {
int mx = 0;
for (int j = 0; j < 26; ++j) {
res += f[i][j];
mx = max(mx, f[i][j]);
}
res -= mx;
}
cout << res << '\n';
}
}
return 0;
}
/*
*/1010. J. Rare Game
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), cnt(n + 1);
for (int i = 1; i <= n; i ++) cin >> a[i];
vector<vector<int>> c(1);
vector<int> cur;
int no4 = 0;
for (int i = 1; i <= n; i ++) {
cnt[a[i]] ++;
if (cnt[a[i]] == 1) {
no4 ++;
cur.push_back(a[i]);
} else if (cnt[a[i]] == 4) {
no4 --;
} else if (cnt[a[i]] > 4) {
cout << 0 << '\n';
return;
}
if (no4 == 0) {
for (int v : cur) cnt[v] = 0;
c.push_back(cur);
cur.clear();
}
}
if (no4) {
cout << 0 << '\n';
return;
}
int m = c.size() - 1;
vector<ll> dp(m + 1), pre(m + 1);
vector<int> last(n + 1);
dp[0] = pre[0] = 1;
int right = 1;
for (int i = 1; i <= m; i ++) {
for (int v : c[i]) {
right = max(right, last[v] + 1);
last[v] = i;
}
dp[i] = pre[i - 1];
if (right > 1) dp[i] = (dp[i] - pre[right - 2] + mod) % mod;
pre[i] = (pre[i - 1] + dp[i]) % mod;
}
cout << dp[m] << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("in.txt", "r", stdin);
int t;
cin >> t;
while (t --) solve();
}1011. K. Union MEX
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
int sum = 0;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
sum += a[i];
}
for (int i = 1; i < n; i ++) {
int u, v;
cin >> u >> v;
}
for (int i = 0; i < q; i ++) {
int x;
cin >> x;
if (a[x]) cout << 0 << '\n';
else cout << sum + 1 << '\n';
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t --) solve();
}