Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
long long n;
cin >> n;
cout << max(6LL, n + 1) / 2 * 5 << '\n';
}
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (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 x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int INF = int(1e9);
int W, H;
int x1, y1, x2, y2;
int w, h;
inline bool read() {
if(!(cin >> W >> H))
return false;
cin >> x1 >> y1 >> x2 >> y2;
cin >> w >> h;
return true;
}
inline void solve() {
int ans = INF;
if (x2 - x1 + w <= W) {
ans = min(ans, max(0, w - x1));
ans = min(ans, max(0, x2 - (W - w)));
}
if (y2 - y1 + h <= H) {
ans = min(ans, max(0, h - y1));
ans = min(ans, max(0, y2 - (H - h)));
}
if (ans == INF)
cout << -1 << endl;
else
cout << double(ans) << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
cout << fixed << setprecision(9);
int t; cin >> t;
while(t--) {
(read());
solve();
}
return 0;
}
Идея: 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 INF = 2e9 + 10;
int main() {
int t;
scanf("%d", &t);
forn(_, t){
int n;
scanf("%d", &n);
vector<vector<int>> a(2, vector<int>(n));
forn(i, 2) forn(j, n)
scanf("%d", &a[i][j]);
int ans = INF;
int sum1 = 0, sum2 = 0;
forn(i, n) sum1 += a[0][i];
forn(i, n){
sum1 -= a[0][i];
ans = min(ans, max(sum1, sum2));
sum2 += a[1][i];
}
printf("%d\n", ans);
}
}
1555D - Скажите палиндромам - нет!
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
string s;
cin >> s;
vector<vector<int>> pr(6, vector<int>(n + 1));
string t = "abc";
int cur = 0;
do {
for (int i = 0; i < n; ++i)
pr[cur][i + 1] = pr[cur][i] + (s[i] != t[i % 3]);
++cur;
} while (next_permutation(t.begin(), t.end()));
while (m--) {
int l, r;
cin >> l >> r;
int ans = n;
for (int i = 0; i < 6; ++i)
ans = min(ans, pr[i][r] - pr[i][l - 1]);
cout << ans << "\n";
}
}
Разбор
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 INF = 1e9;
vector<int> t, ps;
void push(int v){
if (v * 2 + 1 < int(ps.size())){
ps[v * 2] += ps[v];
ps[v * 2 + 1] += ps[v];
}
t[v] += ps[v];
ps[v] = 0;
}
void upd(int v, int l, int r, int L, int R, int val){
push(v);
if (L >= R)
return;
if (l == L && r == R){
ps[v] += val;
push(v);
return;
}
int m = (l + r) / 2;
upd(v * 2, l, m, L, min(m, R), val);
upd(v * 2 + 1, m, r, max(m, L), R, val);
t[v] = min(t[v * 2], t[v * 2 + 1]);
}
int get(){
return t[1] + ps[1];
}
struct seg{
int l, r, w;
};
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<seg> a(n);
forn(i, n){
scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].w);
--a[i].l, --a[i].r;
}
--m;
sort(a.begin(), a.end(), [](const seg &a, const seg &b){
return a.w < b.w;
});
t.resize(4 * m);
ps.resize(4 * m);
int ans = INF;
int j = 0;
forn(i, n){
while (j < n && get() == 0){
upd(1, 0, m, a[j].l, a[j].r, 1);
++j;
}
if (get() == 0){
break;
}
ans = min(ans, a[j - 1].w - a[i].w);
upd(1, 0, m, a[i].l, a[i].r, -1);
}
printf("%d\n", ans);
return 0;
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (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 x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int INF = int(1e9);
const li INF64 = li(1e18);
int n, q;
vector< array<int, 3> > es;
inline bool read() {
if(!(cin >> n >> q))
return false;
es.resize(q);
fore (i, 0, q) {
cin >> es[i][0] >> es[i][1] >> es[i][2];
es[i][0]--;
es[i][1]--;
}
return true;
}
vector< vector<pt> > g;
const int LOG = 19;
vector<int> up[LOG];
vector<int> tin, tout;
vector<int> xr;
int T = 0;
void dfs(int v, int p, int curXor) {
tin[v] = T++;
xr[v] = curXor;
up[0][v] = p;
fore (pw, 1, LOG)
up[pw][v] = up[pw - 1][up[pw - 1][v]];
for (auto [to, w] : g[v]) {
if (to == p)
continue;
dfs(to, v, curXor ^ w);
}
tout[v] = T;
}
void buildLCA() {
fore (pw, 0, LOG)
up[pw].resize(n);
tin.assign(n, -1);
tout.assign(n, -1);
xr.assign(n, 0);
T = 0;
fore (v, 0, n) {
if (tin[v] != -1)
continue;
dfs(v, v, 0);
}
}
int isPar(int p, int v) {
return tin[p] <= tin[v] && tout[v] <= tout[p];
}
int lca(int u, int v) {
if (isPar(u, v)) return u;
if (isPar(v, u)) return v;
for (int pw = LOG - 1; pw >= 0; pw--) {
if (!isPar(up[pw][v], u))
v = up[pw][v];
}
return up[0][v];
}
vector<int> par, rk;
void init(int n) {
par.assign(n, 0);
iota(par.begin(), par.end(), 0);
rk.assign(n, 1);
}
int top(int v) {
if (par[v] != v)
return par[v] = top(par[v]);
return v;
}
bool unite(int u, int v) {
u = top(u);
v = top(v);
if (u == v)
return false;
if (rk[u] < rk[v])
swap(u, v);
par[v] = u;
rk[u] += rk[v];
return true;
}
vector<int> F;
void inc(int pos, int val) {
for(; pos < sz(F); pos |= pos + 1)
F[pos] += val;
}
int sum(int pos) {
int ans = 0;
for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
ans += F[pos];
return ans;
}
void addOnPath(int v, int l) {
while (v != l) {
inc(tin[v], 1);
inc(tout[v], -1);
v = up[0][v];
}
}
inline void solve() {
init(n);
g.resize(n);
vector<int> ans(q, -1);
fore (i, 0, q) {
int u = es[i][0];
int v = es[i][1];
int x = es[i][2];
if (unite(u, v)) {
ans[i] = 1;
g[u].emplace_back(v, x);
g[v].emplace_back(u, x);
}
}
buildLCA();
F.assign(2 * n + 5, 0);
fore (i, 0, q) {
if (ans[i] != -1)
continue;
ans[i] = 0;
int u = es[i][0];
int v = es[i][1];
int x = es[i][2];
int xorPath = xr[u] ^ xr[v];
if ((xorPath ^ x) != 1)
continue;
int l = lca(u, v);
int usedOnPath = sum(tin[u]) + sum(tin[v]) - 2 * sum(tin[l]);
if (usedOnPath > 0)
continue;
ans[i] = 1;
addOnPath(u, l);
addOnPath(v, l);
}
for (int res : ans)
cout << (res ? "YES" : "NO") << '\n';
}
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;
}