2026A - Перпендикулярные отрезки
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int X, Y, K;
cin >> X >> Y >> K;
int M = min(X, Y);
cout << "0 0 " << M << " " << M << endl;
cout << "0 " << M << " " << M << " 0" << endl;
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<long long> a(n);
for (auto& x : a) cin >> x;
long long ans = 1e18;
auto upd = [&](vector<long long> a) {
sort(a.begin(), a.end());
for (int i = 1; i < (int)a.size(); ++i)
if (a[i - 1] == a[i]) return;
long long res = 0;
for (int i = 0; i < (int)a.size(); i += 2)
res = max(res, a[i + 1] - a[i]);
ans = min(ans, res);
};
if (n % 2 == 0) {
upd(a);
cout << ans << '\n';
continue;
}
for (int i = 0; i < n; ++i) {
for (int x : {-1, 1}) {
a.push_back(a[i] + x);
upd(a);
a.pop_back();
}
}
cout << ans << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 400043;
char buf[N];
bool can(const string& s, int k)
{
int n = s.size();
vector<int> used(n);
for(int i = n - 1; i >= 0; i--)
if(k > 0 && s[i] == '1')
{
used[i] = 1;
k--;
}
int cur = 0;
for(int i = 0; i < n; i++)
if(used[i])
{
cur--;
if(cur < 0) return false;
}
else cur++;
return true;
}
void solve()
{
int n;
scanf("%d", &n);
scanf("%s", buf);
if(n == 1)
{
puts("1");
return;
}
string s = buf;
int count_1 = 0;
for(auto x : s) if (x == '1') count_1++;
int l = 1;
int r = count_1 + 1;
while(r - l > 1)
{
int mid = (l + r) / 2;
if(can(s, mid))
l = mid;
else
r = mid;
}
long long ans = 0;
for(int i = n - 1; i >= 0; i--)
if(s[i] == '1' && l > 0)
l--;
else
ans += (i + 1);
printf("%lld\n", ans);
}
int main()
{
int t;
scanf("%d", &t);
for(int i = 0; i < t; i++)
solve();
}
Идея: shnirelman
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int n;
vector<long long> a;
vector<long long> pa;
vector<long long> ppa;
vector<long long> start;
vector<long long> block;
vector<long long> pblock;
vector<long long> prefix_sums(vector<long long> v)
{
int k = v.size();
vector<long long> res(k + 1);
for(int i = 0; i < k; i++) res[i + 1] = res[i] + v[i];
return res;
}
long long get_partial(int l, int r1, int r2)
{
// s(l, r1) + s(l, r1 + 1) + ... + s(l, r2 - 1)
if(r2 <= r1) return 0ll;
int cnt = r2 - r1;
long long rem = pa[l] * cnt;
long long add = ppa[r2 + 1] - ppa[r1 + 1];
return add - rem;
}
pair<int, int> convert(long long i)
{
int idx = upper_bound(start.begin(), start.end(), i) - start.begin() - 1;
pair<int, int> res = {idx, i - start[idx] + idx};
return res;
}
long long query(long long l, long long r)
{
pair<int, int> lf = convert(l);
pair<int, int> rg = convert(r);
long long res = pblock[rg.first + 1] - pblock[lf.first];
if(lf.second != lf.first) res -= get_partial(lf.first, lf.first, lf.second);
if(rg.second != n - 1) res -= get_partial(rg.first, rg.second + 1, n);
return res;
}
int main()
{
scanf("%d", &n);
a.resize(n);
for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
pa = prefix_sums(a);
ppa = prefix_sums(pa);
start = {0};
for(int i = n; i >= 1; i--)
start.push_back(start.back() + i);
block.resize(n);
for(int i = 0; i < n; i++)
block[i] = get_partial(i, i, n);
pblock = prefix_sums(block);
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
long long l, r;
scanf("%lld %lld", &l, &r);
printf("%lld\n", query(l - 1, r - 1));
}
}
2026E - Лучшая подпоследовательность
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
template<typename T = int>
struct Dinic {
struct edge {
int u, rev;
T cap, flow;
};
int n, s, t;
T flow;
vector<int> lst;
vector<int> d;
vector<vector<edge>> g;
Dinic() {}
Dinic(int n, int s, int t) : n(n), s(s), t(t) {
g.resize(n);
d.resize(n);
lst.resize(n);
flow = 0;
}
void add_edge(int v, int u, T cap, bool directed = true) {
g[v].push_back({u, sz(g[u]), cap, 0});
g[u].push_back({v, sz(g[v]) - 1, directed ? 0 : cap, 0});
}
T dfs(int v, T flow) {
if (v == t) return flow;
if (flow == 0) return 0;
T result = 0;
for (; lst[v] < sz(g[v]); ++lst[v]) {
edge& e = g[v][lst[v]];
if (d[e.u] != d[v] + 1) continue;
T add = dfs(e.u, min(flow, e.cap - e.flow));
if (add > 0) {
result += add;
flow -= add;
e.flow += add;
g[e.u][e.rev].flow -= add;
}
if (flow == 0) break;
}
return result;
}
bool bfs() {
fill(d.begin(), d.end(), -1);
queue<int> q({s});
d[s] = 0;
while (!q.empty() && d[t] == -1) {
int v = q.front(); q.pop();
for (auto& e : g[v]) {
if (d[e.u] == -1 && e.cap - e.flow > 0) {
q.push(e.u);
d[e.u] = d[v] + 1;
}
}
}
return d[t] != -1;
}
T calc() {
T add;
while (bfs()) {
fill(lst.begin(), lst.end(), 0);
while((add = dfs(s, numeric_limits<T>::max())) > 0)
flow += add;
}
return flow;
}
};
const int B = 60;
const int INF = 1e9;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int s = n + B, t = n + B + 1;
Dinic mf(t + 1, s, t);
for (int i = 0; i < n; ++i) {
long long x;
cin >> x;
mf.add_edge(s, i, 1);
for (int j = 0; j < B; ++j) {
if ((x >> j) & 1) mf.add_edge(i, j + n, INF);
}
}
for (int i = 0; i < B; ++i) mf.add_edge(i + n, t, 1);
cout << n - mf.calc() << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int P = 2000 + 5;
struct item{
int p, t;
};
struct minstack {
stack<item> st;
stack<array<int, P>> dp;
int get(int p) {return dp.empty() ? 0 : dp.top()[p];}
bool empty() {return st.empty();}
int size() {return st.size();}
void push(item it) {
if (empty()){
dp.push({});
for (int i = 0; i < P; ++i)
dp.top()[i] = 0;
}
else{
dp.push(dp.top());
}
st.push(it);
for (int i = P - it.p - 1; i >= 0; --i)
dp.top()[i + it.p] = max(dp.top()[i + it.p], dp.top()[i] + it.t);
}
void pop() {
st.pop();
dp.pop();
}
item top() {
return st.top();
}
void swap(minstack &x) {
st.swap(x.st);
dp.swap(x.dp);
}
};
struct mindeque {
minstack l, r, t;
void rebalance() {
bool f = false;
if (r.empty()) {f = true; l.swap(r);}
int sz = r.size() / 2;
while (sz--) {t.push(r.top()); r.pop();}
while (!r.empty()) {l.push(r.top()); r.pop();}
while (!t.empty()) {r.push(t.top()); t.pop();}
if (f) l.swap(r);
}
int get(int p) {
int ans = 0;
for (int i = 0; i <= p; ++i)
ans = max(ans, l.get(i) + r.get(p - i));
return ans;
}
bool empty() {return l.empty() && r.empty();}
int size() {return l.size() + r.size();}
void push_front(item it) {l.push(it);}
void push_back(item it) {r.push(it);}
void pop_front() {if (l.empty()) rebalance(); l.pop();}
void pop_back() {if (r.empty()) rebalance(); r.pop();}
item front() {if (l.empty()) rebalance(); return l.top();}
item back() {if (r.empty()) rebalance(); return r.top();}
void swap(mindeque &x) {l.swap(x.l); r.swap(x.r);}
};
struct edge{
int u, tp, p, t;
};
struct query{
int i, p;
};
vector<vector<edge>> g;
vector<vector<query>> qs;
vector<int> ans;
mindeque ks;
void dfs(int v){
for (auto& [i, p] : qs[v]){
ans[i] = ks.get(p);
}
for (auto& [u, tp, p, t] : g[v]){
if (tp == 0){
dfs(u);
}
else if (tp == -1){
auto it = ks.front();
ks.pop_front();
dfs(u);
ks.push_front({it.p, it.t});
}
else{
ks.push_back({p, t});
dfs(u);
ks.pop_back();
}
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int q;
cin >> q;
vector<int> st(1);
vector<int> where(q, -1);
int cnt = 1, cnt_real = 1;
where[0] = 0;
g.push_back({});
qs.push_back({});
auto copy_shop = [&](int x, bool real){
g.push_back({});
qs.push_back({});
st.push_back(st[x]);
if (real){
where[cnt_real] = cnt;
++cnt_real;
}
++cnt;
};
forn(i, q){
int tp, x;
cin >> tp >> x;
--x;
int v = where[x], u = -1;
if (tp != 4){
copy_shop(v, tp == 1);
u = cnt - 1;
}
if (tp == 1){
g[v].push_back({u, 0, -1, -1});
continue;
}
if (tp == 3){
g[v].push_back({u, -1, -1, -1});
++st[u];
where[x] = u;
continue;
}
int p;
cin >> p;
if (tp == 4){
qs[v].push_back({i, p});
continue;
}
int t;
cin >> t;
g[v].push_back({u, 1, p, t});
where[x] = u;
}
ans.assign(q, -1);
dfs(0);
forn(i, q) if (ans[i] != -1) cout << ans[i] << '\n';
return 0;
}