Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
val t = readLine()!!.toInt()
for (ct in 1..t) {
val (str, int, exp) = readLine()!!.split(' ').map { it.toInt() }
val minAddStr = maxOf(0, (exp + int - str + 2) / 2)
println(maxOf(exp - minAddStr + 1, 0))
}
}
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int t;
int n, m;
int d[N], h[N];
int main() {
cin >> t;
for(int tc = 0; tc < t; ++tc){
cin >> n >> m;
int maxDH = -2e9;
for(int i = 0; i < n; ++i){
cin >> d[i] >> h[i];
maxDH = max(maxDH, d[i] - h[i]);
}
int res = 1;
int maxD = *max_element(d, d + n);
m -= maxD;
if(m > 0){
if(maxDH <= 0) res = -1;
else res += (m + maxDH - 1) / maxDH;
}
cout << res << endl;
}
return 0;
}
1217C - The Number Of Good Substrings
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
int t;
string s;
int nxt[N];
int main() {
cin >> t;
for(int tc = 0; tc < t; ++tc){
cin >> s;
for(int i = 0; i < s.size(); ++i)
if(s[i] == '1') nxt[i] = i;
else nxt[i] = (i == 0? -1 : nxt[i - 1]);
int res = 0;
for(int r = 0; r < s.size(); ++r){
int sum = 0;
for(int l = r; l >= 0 && r - l < 20; --l){
if(s[l] == '0') continue;
sum += 1 << (r - l);
if(sum <= r - (l == 0? -1 : nxt[l - 1]))
++res;
}
}
cout << res << endl;
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Roms)
#include<bits/stdc++.h>
using namespace std;
const int N = int(1e6) + 55;
int n, m;
vector <pair<int, int> > g[N];
int col[N];
bool cyc;
int res[N];
void dfs(int v){
col[v] = 1;
for(auto p : g[v]){
int to = p.first, id = p.second;
if(col[to] == 0){
dfs(to);
res[id] = 1;
}
else if(col[to] == 2)
res[id] = 1;
else{
res[id] = 2;
cyc = true;
}
}
col[v] = 2;
}
int main(){
cin >> n >> m;
for(int i = 0; i < m; ++i){
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(make_pair(v, i));
}
for(int i = 0; i < n; ++i)
if(col[i] == 0)
dfs(i);
cout << (cyc? 2 : 1) << endl;
for(int i = 0; i < m; ++i) cout << res[i] << ' ';
cout << endl;
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 200 * 1000 + 13;
const int INF = 2e9;
const int LOGN = 9;
struct node{
int best;
int mn[LOGN];
node(){
best = INF;
forn(i, LOGN)
mn[i] = INF;
}
int& operator [](int x){
return mn[x];
}
};
int a[N];
node t[4 * N];
void upd(node &t, int val){
int x = val;
forn(i, LOGN){
if (x % 10 != 0)
t[i] = min(t[i], val);
x /= 10;
}
}
node merge(node &a, node &b){
node c;
c.best = min(a.best, b.best);
forn(i, LOGN){
c[i] = min(a[i], b[i]);
if (a[i] < INF && b[i] < INF)
c.best = min(c.best, a[i] + b[i]);
}
return c;
}
void build(int v, int l, int r){
if (l == r - 1){
t[v] = node();
upd(t[v], a[l]);
return;
}
int m = (l + r) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m, r);
t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
void upd(int v, int l, int r, int pos, int val){
if (l == r - 1){
t[v] = node();
upd(t[v], val);
return;
}
int m = (l + r) / 2;
if (pos < m)
upd(v * 2, l, m, pos, val);
else
upd(v * 2 + 1, m, r, pos, val);
t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
node get(int v, int l, int r, int L, int R){
if (l == L && r == R)
return t[v];
int m = (l + r) / 2;
if (R <= m)
return get(v * 2, l, m, L, R);
if (L >= m)
return get(v * 2 + 1, m, r, L, R);
node ln = get(v * 2, l, m, L, m);
node rn = get(v * 2 + 1, m, r, m, R);
return merge(ln, rn);
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
forn(i, n)
scanf("%d", &a[i]);
build(1, 0, n);
forn(i, m){
int t, x, y;
scanf("%d%d%d", &t, &x, &y);
--x;
if (t == 1)
upd(1, 0, n, x, y);
else{
node res = get(1, 0, n, x, y);
printf("%d\n", res.best == INF ? -1 : res.best);
}
}
return 0;
}
1217F - Forced Online Queries Problem
Идея: BledDest
Разбор
Tutorial is loading...
Решение (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int BUF = 10 * 1000 * 1000 + 13;
const int N = 300 * 1000 + 13;
const int M = 300 * 1000 + 13;
const int P = 400;
struct query{
int t, x, y;
int e0, e1;
};
int n, m;
query q[M];
int p[N], rk[N];
int cnt;
int* where[BUF];
int val[BUF];
void rollback(){
while (cnt > 0){
*where[cnt - 1] = val[cnt - 1];
--cnt;
}
}
int getp(int a){
return (a == p[a] ? a : getp(p[a]));
}
void unite(int a, int b){
a = getp(a), b = getp(b);
if (a == b) return;
if (rk[a] < rk[b]) swap(a, b);
where[cnt] = &rk[a];
val[cnt++] = rk[a];
where[cnt] = &p[b];
val[cnt++] = p[b];
assert(cnt <= BUF);
rk[a] += rk[b];
p[b] = a;
}
int getpFast(int a){
return (a == p[a] ? a : p[a] = getpFast(p[a]));
}
void uniteFast(int a, int b){
a = getpFast(a), b = getpFast(b);
if (a == b) return;
if (rk[a] < rk[b]) swap(a, b);
rk[a] += rk[b];
p[b] = a;
}
struct edge{
int v, u;
};
bool operator <(const edge &a, const edge &b){
if (a.v != b.v)
return a.v < b.v;
return a.u < b.u;
}
edge edges[2 * M];
map<edge, int> rev;
bool used[2 * M];
bool state[2 * M];
int ans[M];
vector<int> cur;
void rebuild(int l){
int r = min(m, l + P);
forn(i, n) p[i] = i, rk[i] = 1;
memset(used, 0, sizeof(used));
memset(state, 0, sizeof(state));
forn(i, l) if (q[i].t == 1){
int e = (ans[i] ? q[i].e1 : q[i].e0);
used[e] = true;
state[e] ^= 1;
}
for (int i = l; i < r; ++i) if (q[i].t == 1)
used[q[i].e0] = used[q[i].e1] = false;
cur.clear();
cnt = 0;
forn(i, l) if (q[i].t == 1){
int e = (ans[i] ? q[i].e1 : q[i].e0);
if (used[e] && state[e]){
state[e] = false;
uniteFast(edges[e].v, edges[e].u);
}
else if (!used[e] && state[e]){
state[e] = false;
cur.push_back(e);
}
}
}
int get_edge(edge e){
if (!rev.count(e)){
int k = rev.size();
edges[k] = e;
rev[e] = k;
}
return rev[e];
}
int main(){
scanf("%d%d", &n, &m);
forn(i, m){
scanf("%d%d%d", &q[i].t, &q[i].x, &q[i].y);
--q[i].x, --q[i].y;
if (q[i].t == 1){
edge e({q[i].x, q[i].y});
if (e.v > e.u) swap(e.v, e.u);
q[i].e0 = get_edge(e);
e.v = (e.v + 1) % n, e.u = (e.u + 1) % n;
if (e.v > e.u) swap(e.v, e.u);
q[i].e1 = get_edge(e);
}
}
string res = "";
ans[0] = 0;
forn(i, m){
if (i % P == 0)
rebuild(i);
int x = (q[i].x + ans[i]) % n;
int y = (q[i].y + ans[i]) % n;
if (x > y) swap(x, y);
if (q[i].t == 1){
rollback();
int e = get_edge({x, y});
auto it = find(cur.begin(), cur.end(), e);
if (it == cur.end())
cur.push_back(e);
else
cur.erase(it);
ans[i + 1] = ans[i];
}
else{
for (auto e : cur)
unite(edges[e].v, edges[e].u);
bool rc = (getp(x) == getp(y));
ans[i + 1] = rc;
res += ('0' + rc);
}
}
puts(res.c_str());
return 0;
}