Thank you for your participation!↵
↵
Problem A, B were authored by [user:djm03178,2025-10-03].↵
↵
Problem C was authored by [user:As_dfsdf,2025-10-03].↵
↵
Problem D was authored by [user:qwerasdfzxcl,2025-10-03].↵
↵
Problem E, F, G, H1, H2 were authored by [user:ko_osaga,2025-10-03].↵
↵
[problem:2152A]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152A]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
↵
int t;↵
cin >> t;↵
while (t--)↵
{↵
int n;↵
cin >> n;↵
set<int> s;↵
for (int i = 0; i < n; i++)↵
{↵
int x;↵
cin >> x;↵
s.insert(x);↵
}↵
cout << s.size() * 2 - 1 << '\n';↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2152B]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152B]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
↵
[problem:2152A]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152A]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
[problem:2152C]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152C]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
[problem:2152D]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152D]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
[problem:2152E]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152E]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
[problem:2152F]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152F]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
[problem:2152G]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152G]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
[problem:2152H1]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152H1]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
[problem:2152H2]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152H2]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
↵
int t;↵
cin >> t;↵
while (t--)↵
{↵
int n, ra, ca, rb, cb;↵
cin >> n >> ra >> ca >> rb >> cb;↵
int ans = 0;↵
if (rb > ra)↵
ans = max(ans, rb);↵
else if (rb < ra)↵
ans = max(ans, n - rb);↵
if (cb > ca)↵
ans = max(ans, cb);↵
else if (cb < ca)↵
ans = max(ans, n - cb);↵
cout << ans << '\n';↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
[problem:2152C]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152C]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
/*↵
* T1 Thanks Round↵
* Problem triple-removal↵
* Main Correct Solution↵
*/↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int MAX = 250'010;↵
↵
int A[MAX];↵
↵
int diff[MAX];↵
int diffsum[MAX];↵
↵
int sum[2][MAX];↵
↵
void solve() {↵
int N, Q;↵
cin >> N >> Q;↵
int i;↵
for (i = 1; i <= N; i++) cin >> A[i];↵
for (i = 1; i <= N; i++) {↵
sum[0][i] = sum[0][i - 1];↵
sum[1][i] = sum[1][i - 1];↵
sum[A[i]][i]++;↵
↵
diff[i] = A[i] != A[i - 1];↵
diffsum[i] = diffsum[i - 1] + diff[i];↵
}↵
int l, r;↵
for (i = 1; i <= Q; i++) {↵
cin >> l >> r;↵
↵
int z, o;↵
z = sum[0][r] - sum[0][l - 1];↵
o = sum[1][r] - sum[1][l - 1];↵
if (z % 3) {↵
cout << -1 << '\n';↵
continue;↵
}↵
if (o % 3) {↵
cout << -1 << '\n';↵
continue;↵
}↵
↵
int sum = z / 3 + o / 3;↵
if (diffsum[r] - diffsum[l] == (r - l)) sum++;↵
cout << sum << '\n';↵
}↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false), cin.tie(0);↵
int t, T;↵
cin >> T;↵
for (t = 1; t <= T; t++) solve();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2152D]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152D]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
constexpr int MAXN = 250000;↵
↵
int a[MAXN + 100];↵
ll prf[MAXN + 100][4];↵
↵
void solve(){↵
int n, q;↵
scanf("%d %d", &n, &q);↵
↵
for (int i=1;i<=n;i++) scanf("%d", a+i);↵
↵
for (int i=1;i<=n;i++){↵
for (int j=0;j<3;j++) prf[i][j] = prf[i-1][j];↵
↵
int typ = 2;↵
if (popcount((unsigned)a[i]) == 1) typ = 0;↵
else if (popcount((unsigned)a[i]-1) == 1) typ = 1;↵
↵
prf[i][typ]++;↵
↵
prf[i][3] = prf[i-1][3] + (31 - countl_zero((unsigned)a[i]));↵
}↵
↵
while(q--){↵
int l, r;↵
scanf("%d %d", &l, &r);↵
↵
ll cnt[3] = {0};↵
for (int j=0;j<3;j++) cnt[j] = prf[r][j] - prf[l-1][j];↵
↵
ll ans = prf[r][3] - prf[l-1][3] + cnt[2] + cnt[1] / 2;↵
printf("%lld\n", ans);↵
}↵
}↵
↵
int main(){↵
int t;↵
scanf("%d", &t);↵
↵
while(t--) solve();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2152E]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152E]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
using lint = long long;↵
using pi = array<lint, 2>;↵
#define sz(v) ((int)(v).size())↵
#define all(v) (v).begin(), (v).end()↵
#define cr(v, n) (v).clear(), (v).resize(n);↵
↵
void solve() {↵
int n;↵
cin >> n;↵
vector<int> ord(n * n + 1);↵
iota(all(ord), 0);↵
auto query = [&](vector<int> v) {↵
cout << "? " << sz(v);↵
for (auto &x : v)↵
cout << " " << x + 1;↵
cout << endl;↵
int y;↵
cin >> y;↵
v.resize(y);↵
for (auto &x : v)↵
cin >> x, x--;↵
return v;↵
};↵
vector<int> dp(n * n + 1, n);↵
for (int i = 0; i < n; i++) {↵
auto cur_ord = query(ord);↵
if (sz(cur_ord) > n) {↵
cout << "!";↵
for (int i = 0; i < n+1; i++)↵
cout << " " << cur_ord[i] + 1;↵
cout << endl;↵
return;↵
}↵
vector<int> new_ord;↵
for (auto &x : ord) {↵
if (!binary_search(all(cur_ord), x)) {↵
new_ord.push_back(x);↵
} else dp[x] = i;↵
}↵
ord = new_ord;↵
}↵
int cur = n;↵
vector<int> ans;↵
for (int i = n * n; i >= 0; i--) {↵
if (dp[i] == cur) {↵
ans.push_back(i);↵
cur--;↵
}↵
}↵
if(sz(ans) != n + 1){↵
cerr << cur << endl;↵
for(auto &x : dp) cerr << x << " ";↵
cerr << endl;↵
}↵
reverse(all(ans));↵
assert(sz(ans) == n+1);↵
cout << "!";↵
for (auto &x : ans)↵
cout << " " << x + 1;↵
cout << endl;↵
}↵
↵
int main() {↵
int tc;↵
cin >> tc;↵
while (tc--)↵
solve();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2152F]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152F]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
using lint = long long;↵
using pi = array<lint, 2>;↵
#define sz(v) ((int)(v).size())↵
#define all(v) (v).begin(), (v).end()↵
#define cr(v, n) (v).clear(), (v).resize(n);↵
const int MAXN = 500005;↵
↵
int nxt1[20][MAXN], dep1[MAXN];↵
pi nxt2[20][MAXN];↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
↵
int T;↵
cin >> T;↵
↵
while (T--){↵
int n, t;↵
cin >> n >> t;↵
t++;↵
vector<int> a(n);↵
for (int i = 0; i < n; i++)↵
cin >> a[i];↵
↵
// EDIT: added init statements for globals↵
for (int i = 0; i < n+5; i++){↵
for (int j = 0; j < 20; j++) nxt1[j][i]=0,nxt2[j][i]={0,0};↵
dep1[i]=0;↵
}↵
↵
int j = 0;↵
for (int i = 0; i < n; i++) {↵
while (j < n && a[j] < a[i] + t)↵
j++;↵
nxt1[0][i] = j;↵
}↵
nxt1[0][n] = n;↵
for (int i = n - 1; i >= 0; i--)↵
dep1[i] = dep1[nxt1[0][i]] + 1;↵
for (int i = 1; i < 20; i++) {↵
for (int j = 0; j <= n; j++)↵
nxt1[i][j] = nxt1[i - 1][nxt1[i - 1][j]];↵
}↵
auto lca = [&](int u, int v) {↵
if (dep1[u] > dep1[v])↵
swap(u, v);↵
int dx = dep1[v] - dep1[u];↵
for (int i = 0; dx; i++) {↵
if (dx & 1) {↵
v = nxt1[i][v];↵
}↵
dx >>= 1;↵
}↵
if (u == v)↵
return u;↵
for (int i = 19; i >= 0; i--) {↵
if (nxt1[i][u] != nxt1[i][v]) {↵
u = nxt1[i][u];↵
v = nxt1[i][v];↵
}↵
}↵
return nxt1[0][u];↵
};↵
for (int i = 0; i < n; i++) {↵
int z = lca(i, i + 1);↵
nxt2[0][i] = pi{z, dep1[i] + dep1[i + 1] - 2 * dep1[z]};↵
}↵
nxt2[0][n] = pi{n, 0};↵
for (int i = 1; i < 20; i++) {↵
for (int j = 0; j <= n; j++) {↵
auto [n1, d1] = nxt2[i - 1][j];↵
auto [n2, d2] = nxt2[i - 1][n1];↵
nxt2[i][j] = pi{n2, d1 + d2};↵
}↵
}↵
auto gp = [&](int l, int r) {↵
int ans = 0;↵
for (int i = 19; i >= 0; i--) {↵
if (nxt1[i][l] < r) {↵
l = nxt1[i][l];↵
ans += (1 << i);↵
}↵
}↵
return ans + 1;↵
};↵
int q;↵
cin >> q;↵
while (q--) {↵
int l, r;↵
cin >> l >> r;↵
l--;↵
if (r - l <= 2) {↵
cout << r - l << "\n";↵
continue;↵
}↵
int ans = 0;↵
for (int i = 19; i >= 0; i--) {↵
if (nxt2[i][l][0] < r) {↵
ans += nxt2[i][l][1];↵
l = nxt2[i][l][0];↵
}↵
}↵
if (l + 1 <= r)↵
ans += gp(l, r);↵
if (l + 2 <= r)↵
ans += gp(l + 1, r);↵
cout << ans << "\n";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2152G]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152G]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
using lint = long long;↵
using pi = array<lint, 2>;↵
#define sz(a) ((int)(a).size())↵
#define all(a) (a).begin(), (a).end()↵
const int MAXN = 250005;↵
const int MAXT = 1050000;↵
↵
struct mtrx {↵
int nxt[2];↵
mtrx() { nxt[0] = nxt[1] = 0; }↵
mtrx(int x) {↵
nxt[x] = 1;↵
nxt[1 ^ x] = 0;↵
}↵
mtrx operator+(const mtrx &m) const {↵
mtrx ret;↵
ret.nxt[0] = nxt[0] + m.nxt[nxt[0] % 2];↵
ret.nxt[1] = nxt[1] + m.nxt[(1 + nxt[1]) % 2];↵
return ret;↵
}↵
};↵
↵
struct node {↵
mtrx M[2];↵
int lazy;↵
node operator+(const node &nd) const {↵
node ret;↵
ret.M[0] = M[0] + nd.M[0];↵
ret.M[1] = M[1] + nd.M[1];↵
ret.lazy = 0;↵
return ret;↵
}↵
} tree[MAXT];↵
↵
void init(int s, int e, int p, vector<pi> &seq) {↵
if (s == e) {↵
tree[p].M[seq[s][0]] = mtrx(seq[s][1]);↵
tree[p].M[1 ^ seq[s][0]] = mtrx();↵
return;↵
}↵
int m = (s + e) / 2;↵
init(s, m, 2 * p, seq);↵
init(m + 1, e, 2 * p + 1, seq);↵
tree[p] = tree[2 * p] + tree[2 * p + 1];↵
}↵
↵
void lazydown(int p) {↵
if (tree[p].lazy) {↵
for (int i = 2 * p; i < 2 * p + 2; i++) {↵
tree[i].lazy ^= 1;↵
swap(tree[i].M[0], tree[i].M[1]);↵
}↵
tree[p].lazy = 0;↵
}↵
}↵
↵
void update(int s, int e, int ps, int pe, int p) {↵
if (e < ps || pe < s)↵
return;↵
if (s <= ps && pe <= e) {↵
tree[p].lazy ^= 1;↵
swap(tree[p].M[0], tree[p].M[1]);↵
return;↵
}↵
int pm = (ps + pe) / 2;↵
lazydown(p);↵
update(s, e, ps, pm, 2 * p);↵
update(s, e, pm + 1, pe, 2 * p + 1);↵
tree[p] = tree[2 * p] + tree[2 * p + 1];↵
}↵
↵
int query() { return tree[1].M[1].nxt[0] / 2; }↵
↵
vector<int> gph[MAXN];↵
int a[MAXN], din[MAXN], dout[MAXN];↵
vector<pi> seq;↵
↵
void dfs(int x, int p = -1) {↵
din[x] = sz(seq);↵
seq.push_back({a[x], 0});↵
for (auto &y : gph[x]) {↵
if (y != p)↵
dfs(y, x);↵
}↵
seq.push_back({a[x], 1});↵
dout[x] = sz(seq);↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
int T; cin >> T;↵
while (T--) {↵
int n;↵
cin >> n;↵
for (int i = 0; i < n; i++)↵
cin >> a[i];↵
↵
for (int i = 0; i < n; i++) gph[i].clear();↵
seq.clear();↵
↵
for (int i = 0; i < n - 1; i++) {↵
int u, v;↵
cin >> u >> v;↵
u--;↵
v--;↵
gph[u].push_back(v);↵
gph[v].push_back(u);↵
}↵
dfs(0);↵
init(0, sz(seq) - 1, 1, seq);↵
cout << query() << "\n";↵
int q;↵
cin >> q;↵
while (q--) {↵
int v;↵
cin >> v;↵
v--;↵
update(din[v], dout[v] - 1, 0, sz(seq) - 1, 1);↵
cout << query() << "\n";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2152H1]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152H1]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
using lint = long long;↵
using pi = array<lint, 2>;↵
#define sz(v) ((int)(v).size())↵
#define all(v) (v).begin(), (v).end()↵
#define cr(v, n) (v).clear(), (v).resize(n);↵
↵
vector<int> pa;↵
↵
int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
int T; cin>>T;↵
while (T--){↵
int n;↵
cin >> n;↵
vector<array<lint, 3>> edges;↵
for (int i = 0; i < n - 1; i++) {↵
lint u, v, w;↵
cin >> u >> v >> w;↵
u--;↵
v--;↵
edges.push_back({w, u, v});↵
}↵
sort(all(edges));↵
reverse(all(edges));↵
cr(pa, 2 * n - 1);↵
vector<lint> cost(2 * n - 1);↵
vector<pi> ch(2 * n - 1);↵
iota(all(pa), 0);↵
for (int i = 0; i < n - 1; i++) {↵
int u = find(edges[i][1]);↵
int v = find(edges[i][2]);↵
pa[u] = i + n;↵
pa[v] = i + n;↵
ch[i + n] = {u, v};↵
cost[edges[i][1]] += edges[i][0];↵
cost[edges[i][2]] += edges[i][0];↵
cost[i + n] -= edges[i][0] * 2;↵
}↵
for (int i = n; i < 2 * n - 1; i++) {↵
cost[i] += cost[ch[i][0]] + cost[ch[i][1]];↵
}↵
int q;↵
cin >> q;↵
while (q--) {↵
lint x;↵
cin >> x;↵
vector<lint> dp(2 * n - 1);↵
lint dap = 0;↵
for (int i = 0; i < 2 * n - 1; i++) {↵
if (i >= n) {↵
dp[i] += dp[ch[i][0]] + dp[ch[i][1]];↵
}↵
if (dp[i] + cost[i] < x) {↵
dap += x - cost[i] - dp[i];↵
dp[i] = x - cost[i];↵
}↵
}↵
cout << dap << "\n";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2152H2]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152H2]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
using lint = long long;↵
using pi = array<lint, 2>;↵
#define sz(v) ((int)(v).size())↵
#define all(v) (v).begin(), (v).end()↵
#define cr(v, n) (v).clear(), (v).resize(n);↵
↵
vector<int> pa;↵
↵
int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
int T; cin>>T;↵
while (T--){↵
int n;↵
cin >> n;↵
vector<array<lint, 3>> edges;↵
for (int i = 0; i < n - 1; i++) {↵
lint u, v, w;↵
cin >> u >> v >> w;↵
u--;↵
v--;↵
edges.push_back({w, u, v});↵
}↵
sort(all(edges));↵
reverse(all(edges));↵
cr(pa, 2 * n - 1);↵
vector<lint> cost(2 * n - 1);↵
vector<pi> ch(2 * n - 1);↵
iota(all(pa), 0);↵
for (int i = 0; i < n - 1; i++) {↵
int u = find(edges[i][1]);↵
int v = find(edges[i][2]);↵
pa[u] = i + n;↵
pa[v] = i + n;↵
ch[i + n] = {u, v};↵
cost[edges[i][1]] += edges[i][0];↵
cost[edges[i][2]] += edges[i][0];↵
cost[i + n] -= edges[i][0] * 2;↵
}↵
for (int i = n; i < 2 * n - 1; i++) {↵
cost[i] += cost[ch[i][0]] + cost[ch[i][1]];↵
}↵
// (point, slope increase)↵
vector<priority_queue<pi, vector<pi>, greater<pi>>> pq(n);↵
vector<int> idx(2 * n - 1);↵
iota(all(idx), 0);↵
for (int i = 0; i < 2 * n - 1; i++) {↵
if (i < n) {↵
pq[i].push({cost[i], 1});↵
continue;↵
}↵
if (sz(pq[idx[ch[i][0]]]) < sz(pq[idx[ch[i][1]]]))↵
swap(ch[i][0], ch[i][1]);↵
idx[i] = idx[ch[i][0]];↵
while (sz(pq[idx[ch[i][1]]])) {↵
auto tp = pq[idx[ch[i][1]]].top();↵
pq[idx[ch[i][1]]].pop();↵
pq[idx[i]].push(tp);↵
}↵
if (cost[i] >= pq[idx[i]].top()[0])↵
continue;↵
if (cost[i] >= lint(2e9))↵
continue;↵
lint A = 0, B = 0;↵
lint pv = -1;↵
while (sz(pq[idx[i]])) {↵
auto [point, slope] = pq[idx[i]].top();↵
pq[idx[i]].pop();↵
B += A * (point - pv);↵
pv = point;↵
A += slope;↵
// A x - A * pv + B = x - cost[i]↵
// (A - 1) x = A * pv - B - cost[i]↵
lint U = A * pv - B - cost[i];↵
lint L = A - 1;↵
// point <= U / L, so no need to dedup↵
if (L > 0) {↵
assert(point * L <= U);↵
if ((sz(pq[idx[i]]) == 0 || U < pq[idx[i]].top()[0] * L)) {↵
lint f1 = U / L - cost[i];↵
lint f2 = (U / L + 1 - pv) * A + B;↵
// (cost[i], 0) -> (U / L, f1) -> (U / L + 1, f2) -> increase w/ speed A↵
pq[idx[i]].push({cost[i], 1});↵
pq[idx[i]].push({U / L, f2 - f1 - 1});↵
pq[idx[i]].push({U / L + 1, A - (f2 - f1)});↵
break;↵
}↵
} else if (sz(pq[idx[i]]) == 0) {↵
pq[idx[i]].push({cost[i], 1});↵
break;↵
}↵
}↵
}↵
int q;↵
cin >> q;↵
vector<pi> queries(q);↵
for (int i = 0; i < q; i++) {↵
cin >> queries[i][0];↵
queries[i][1] = i;↵
}↵
sort(all(queries));↵
vector<lint> ans(q);↵
lint A = 0, B = 0, pv = -1;↵
auto T = idx[2 * n - 2];↵
for (auto &[x, i] : queries) {↵
while (sz(pq[T]) && pq[T].top()[0] <= x) {↵
auto [point, slope] = pq[T].top();↵
pq[T].pop();↵
B += A * (point - pv);↵
pv = point;↵
A += slope;↵
}↵
ans[i] = (x - pv) * A + B;↵
}↵
for (auto &v : ans)↵
cout << v << "\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
Problem A, B were authored by [user:djm03178,2025-10-03].↵
↵
Problem C was authored by [user:As_dfsdf,2025-10-03].↵
↵
Problem D was authored by [user:qwerasdfzxcl,2025-10-03].↵
↵
Problem E, F, G, H1, H2 were authored by [user:ko_osaga,2025-10-03].↵
↵
[problem:2152A]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152A]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
↵
int t;↵
cin >> t;↵
while (t--)↵
{↵
int n;↵
cin >> n;↵
set<int> s;↵
for (int i = 0; i < n; i++)↵
{↵
int x;↵
cin >> x;↵
s.insert(x);↵
}↵
cout << s.size() * 2 - 1 << '\n';↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2152B]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152B]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
↵
↵
[problem:2152A]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152A]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
[problem:2152C]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152C]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
[problem:2152D]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152D]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
[problem:2152E]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152E]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
[problem:2152F]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152F]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
[problem:2152G]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152G]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
[problem:2152H1]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152H1]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
</spoiler>↵
↵
[problem:2152H2]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152H2]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
↵
int t;↵
cin >> t;↵
while (t--)↵
{↵
int n, ra, ca, rb, cb;↵
cin >> n >> ra >> ca >> rb >> cb;↵
int ans = 0;↵
if (rb > ra)↵
ans = max(ans, rb);↵
else if (rb < ra)↵
ans = max(ans, n - rb);↵
if (cb > ca)↵
ans = max(ans, cb);↵
else if (cb < ca)↵
ans = max(ans, n - cb);↵
cout << ans << '\n';↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
[problem:2152C]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152C]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
/*↵
* T1 Thanks Round↵
* Problem triple-removal↵
* Main Correct Solution↵
*/↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int MAX = 250'010;↵
↵
int A[MAX];↵
↵
int diff[MAX];↵
int diffsum[MAX];↵
↵
int sum[2][MAX];↵
↵
void solve() {↵
int N, Q;↵
cin >> N >> Q;↵
int i;↵
for (i = 1; i <= N; i++) cin >> A[i];↵
for (i = 1; i <= N; i++) {↵
sum[0][i] = sum[0][i - 1];↵
sum[1][i] = sum[1][i - 1];↵
sum[A[i]][i]++;↵
↵
diff[i] = A[i] != A[i - 1];↵
diffsum[i] = diffsum[i - 1] + diff[i];↵
}↵
int l, r;↵
for (i = 1; i <= Q; i++) {↵
cin >> l >> r;↵
↵
int z, o;↵
z = sum[0][r] - sum[0][l - 1];↵
o = sum[1][r] - sum[1][l - 1];↵
if (z % 3) {↵
cout << -1 << '\n';↵
continue;↵
}↵
if (o % 3) {↵
cout << -1 << '\n';↵
continue;↵
}↵
↵
int sum = z / 3 + o / 3;↵
if (diffsum[r] - diffsum[l] == (r - l)) sum++;↵
cout << sum << '\n';↵
}↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false), cin.tie(0);↵
int t, T;↵
cin >> T;↵
for (t = 1; t <= T; t++) solve();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2152D]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152D]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
constexpr int MAXN = 250000;↵
↵
int a[MAXN + 100];↵
ll prf[MAXN + 100][4];↵
↵
void solve(){↵
int n, q;↵
scanf("%d %d", &n, &q);↵
↵
for (int i=1;i<=n;i++) scanf("%d", a+i);↵
↵
for (int i=1;i<=n;i++){↵
for (int j=0;j<3;j++) prf[i][j] = prf[i-1][j];↵
↵
int typ = 2;↵
if (popcount((unsigned)a[i]) == 1) typ = 0;↵
else if (popcount((unsigned)a[i]-1) == 1) typ = 1;↵
↵
prf[i][typ]++;↵
↵
prf[i][3] = prf[i-1][3] + (31 - countl_zero((unsigned)a[i]));↵
}↵
↵
while(q--){↵
int l, r;↵
scanf("%d %d", &l, &r);↵
↵
ll cnt[3] = {0};↵
for (int j=0;j<3;j++) cnt[j] = prf[r][j] - prf[l-1][j];↵
↵
ll ans = prf[r][3] - prf[l-1][3] + cnt[2] + cnt[1] / 2;↵
printf("%lld\n", ans);↵
}↵
}↵
↵
int main(){↵
int t;↵
scanf("%d", &t);↵
↵
while(t--) solve();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2152E]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152E]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
using lint = long long;↵
using pi = array<lint, 2>;↵
#define sz(v) ((int)(v).size())↵
#define all(v) (v).begin(), (v).end()↵
#define cr(v, n) (v).clear(), (v).resize(n);↵
↵
void solve() {↵
int n;↵
cin >> n;↵
vector<int> ord(n * n + 1);↵
iota(all(ord), 0);↵
auto query = [&](vector<int> v) {↵
cout << "? " << sz(v);↵
for (auto &x : v)↵
cout << " " << x + 1;↵
cout << endl;↵
int y;↵
cin >> y;↵
v.resize(y);↵
for (auto &x : v)↵
cin >> x, x--;↵
return v;↵
};↵
vector<int> dp(n * n + 1, n);↵
for (int i = 0; i < n; i++) {↵
auto cur_ord = query(ord);↵
if (sz(cur_ord) > n) {↵
cout << "!";↵
for (int i = 0; i < n+1; i++)↵
cout << " " << cur_ord[i] + 1;↵
cout << endl;↵
return;↵
}↵
vector<int> new_ord;↵
for (auto &x : ord) {↵
if (!binary_search(all(cur_ord), x)) {↵
new_ord.push_back(x);↵
} else dp[x] = i;↵
}↵
ord = new_ord;↵
}↵
int cur = n;↵
vector<int> ans;↵
for (int i = n * n; i >= 0; i--) {↵
if (dp[i] == cur) {↵
ans.push_back(i);↵
cur--;↵
}↵
}↵
if(sz(ans) != n + 1){↵
cerr << cur << endl;↵
for(auto &x : dp) cerr << x << " ";↵
cerr << endl;↵
}↵
reverse(all(ans));↵
assert(sz(ans) == n+1);↵
cout << "!";↵
for (auto &x : ans)↵
cout << " " << x + 1;↵
cout << endl;↵
}↵
↵
int main() {↵
int tc;↵
cin >> tc;↵
while (tc--)↵
solve();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2152F]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152F]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
using lint = long long;↵
using pi = array<lint, 2>;↵
#define sz(v) ((int)(v).size())↵
#define all(v) (v).begin(), (v).end()↵
#define cr(v, n) (v).clear(), (v).resize(n);↵
const int MAXN = 500005;↵
↵
int nxt1[20][MAXN], dep1[MAXN];↵
pi nxt2[20][MAXN];↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
↵
int T;↵
cin >> T;↵
↵
while (T--){↵
int n, t;↵
cin >> n >> t;↵
t++;↵
vector<int> a(n);↵
for (int i = 0; i < n; i++)↵
cin >> a[i];↵
↵
// EDIT: added init statements for globals↵
for (int i = 0; i < n+5; i++){↵
for (int j = 0; j < 20; j++) nxt1[j][i]=0,nxt2[j][i]={0,0};↵
dep1[i]=0;↵
}↵
↵
int j = 0;↵
for (int i = 0; i < n; i++) {↵
while (j < n && a[j] < a[i] + t)↵
j++;↵
nxt1[0][i] = j;↵
}↵
nxt1[0][n] = n;↵
for (int i = n - 1; i >= 0; i--)↵
dep1[i] = dep1[nxt1[0][i]] + 1;↵
for (int i = 1; i < 20; i++) {↵
for (int j = 0; j <= n; j++)↵
nxt1[i][j] = nxt1[i - 1][nxt1[i - 1][j]];↵
}↵
auto lca = [&](int u, int v) {↵
if (dep1[u] > dep1[v])↵
swap(u, v);↵
int dx = dep1[v] - dep1[u];↵
for (int i = 0; dx; i++) {↵
if (dx & 1) {↵
v = nxt1[i][v];↵
}↵
dx >>= 1;↵
}↵
if (u == v)↵
return u;↵
for (int i = 19; i >= 0; i--) {↵
if (nxt1[i][u] != nxt1[i][v]) {↵
u = nxt1[i][u];↵
v = nxt1[i][v];↵
}↵
}↵
return nxt1[0][u];↵
};↵
for (int i = 0; i < n; i++) {↵
int z = lca(i, i + 1);↵
nxt2[0][i] = pi{z, dep1[i] + dep1[i + 1] - 2 * dep1[z]};↵
}↵
nxt2[0][n] = pi{n, 0};↵
for (int i = 1; i < 20; i++) {↵
for (int j = 0; j <= n; j++) {↵
auto [n1, d1] = nxt2[i - 1][j];↵
auto [n2, d2] = nxt2[i - 1][n1];↵
nxt2[i][j] = pi{n2, d1 + d2};↵
}↵
}↵
auto gp = [&](int l, int r) {↵
int ans = 0;↵
for (int i = 19; i >= 0; i--) {↵
if (nxt1[i][l] < r) {↵
l = nxt1[i][l];↵
ans += (1 << i);↵
}↵
}↵
return ans + 1;↵
};↵
int q;↵
cin >> q;↵
while (q--) {↵
int l, r;↵
cin >> l >> r;↵
l--;↵
if (r - l <= 2) {↵
cout << r - l << "\n";↵
continue;↵
}↵
int ans = 0;↵
for (int i = 19; i >= 0; i--) {↵
if (nxt2[i][l][0] < r) {↵
ans += nxt2[i][l][1];↵
l = nxt2[i][l][0];↵
}↵
}↵
if (l + 1 <= r)↵
ans += gp(l, r);↵
if (l + 2 <= r)↵
ans += gp(l + 1, r);↵
cout << ans << "\n";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2152G]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152G]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
using lint = long long;↵
using pi = array<lint, 2>;↵
#define sz(a) ((int)(a).size())↵
#define all(a) (a).begin(), (a).end()↵
const int MAXN = 250005;↵
const int MAXT = 1050000;↵
↵
struct mtrx {↵
int nxt[2];↵
mtrx() { nxt[0] = nxt[1] = 0; }↵
mtrx(int x) {↵
nxt[x] = 1;↵
nxt[1 ^ x] = 0;↵
}↵
mtrx operator+(const mtrx &m) const {↵
mtrx ret;↵
ret.nxt[0] = nxt[0] + m.nxt[nxt[0] % 2];↵
ret.nxt[1] = nxt[1] + m.nxt[(1 + nxt[1]) % 2];↵
return ret;↵
}↵
};↵
↵
struct node {↵
mtrx M[2];↵
int lazy;↵
node operator+(const node &nd) const {↵
node ret;↵
ret.M[0] = M[0] + nd.M[0];↵
ret.M[1] = M[1] + nd.M[1];↵
ret.lazy = 0;↵
return ret;↵
}↵
} tree[MAXT];↵
↵
void init(int s, int e, int p, vector<pi> &seq) {↵
if (s == e) {↵
tree[p].M[seq[s][0]] = mtrx(seq[s][1]);↵
tree[p].M[1 ^ seq[s][0]] = mtrx();↵
return;↵
}↵
int m = (s + e) / 2;↵
init(s, m, 2 * p, seq);↵
init(m + 1, e, 2 * p + 1, seq);↵
tree[p] = tree[2 * p] + tree[2 * p + 1];↵
}↵
↵
void lazydown(int p) {↵
if (tree[p].lazy) {↵
for (int i = 2 * p; i < 2 * p + 2; i++) {↵
tree[i].lazy ^= 1;↵
swap(tree[i].M[0], tree[i].M[1]);↵
}↵
tree[p].lazy = 0;↵
}↵
}↵
↵
void update(int s, int e, int ps, int pe, int p) {↵
if (e < ps || pe < s)↵
return;↵
if (s <= ps && pe <= e) {↵
tree[p].lazy ^= 1;↵
swap(tree[p].M[0], tree[p].M[1]);↵
return;↵
}↵
int pm = (ps + pe) / 2;↵
lazydown(p);↵
update(s, e, ps, pm, 2 * p);↵
update(s, e, pm + 1, pe, 2 * p + 1);↵
tree[p] = tree[2 * p] + tree[2 * p + 1];↵
}↵
↵
int query() { return tree[1].M[1].nxt[0] / 2; }↵
↵
vector<int> gph[MAXN];↵
int a[MAXN], din[MAXN], dout[MAXN];↵
vector<pi> seq;↵
↵
void dfs(int x, int p = -1) {↵
din[x] = sz(seq);↵
seq.push_back({a[x], 0});↵
for (auto &y : gph[x]) {↵
if (y != p)↵
dfs(y, x);↵
}↵
seq.push_back({a[x], 1});↵
dout[x] = sz(seq);↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
int T; cin >> T;↵
while (T--) {↵
int n;↵
cin >> n;↵
for (int i = 0; i < n; i++)↵
cin >> a[i];↵
↵
for (int i = 0; i < n; i++) gph[i].clear();↵
seq.clear();↵
↵
for (int i = 0; i < n - 1; i++) {↵
int u, v;↵
cin >> u >> v;↵
u--;↵
v--;↵
gph[u].push_back(v);↵
gph[v].push_back(u);↵
}↵
dfs(0);↵
init(0, sz(seq) - 1, 1, seq);↵
cout << query() << "\n";↵
int q;↵
cin >> q;↵
while (q--) {↵
int v;↵
cin >> v;↵
v--;↵
update(din[v], dout[v] - 1, 0, sz(seq) - 1, 1);↵
cout << query() << "\n";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2152H1]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152H1]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
using lint = long long;↵
using pi = array<lint, 2>;↵
#define sz(v) ((int)(v).size())↵
#define all(v) (v).begin(), (v).end()↵
#define cr(v, n) (v).clear(), (v).resize(n);↵
↵
vector<int> pa;↵
↵
int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
int T; cin>>T;↵
while (T--){↵
int n;↵
cin >> n;↵
vector<array<lint, 3>> edges;↵
for (int i = 0; i < n - 1; i++) {↵
lint u, v, w;↵
cin >> u >> v >> w;↵
u--;↵
v--;↵
edges.push_back({w, u, v});↵
}↵
sort(all(edges));↵
reverse(all(edges));↵
cr(pa, 2 * n - 1);↵
vector<lint> cost(2 * n - 1);↵
vector<pi> ch(2 * n - 1);↵
iota(all(pa), 0);↵
for (int i = 0; i < n - 1; i++) {↵
int u = find(edges[i][1]);↵
int v = find(edges[i][2]);↵
pa[u] = i + n;↵
pa[v] = i + n;↵
ch[i + n] = {u, v};↵
cost[edges[i][1]] += edges[i][0];↵
cost[edges[i][2]] += edges[i][0];↵
cost[i + n] -= edges[i][0] * 2;↵
}↵
for (int i = n; i < 2 * n - 1; i++) {↵
cost[i] += cost[ch[i][0]] + cost[ch[i][1]];↵
}↵
int q;↵
cin >> q;↵
while (q--) {↵
lint x;↵
cin >> x;↵
vector<lint> dp(2 * n - 1);↵
lint dap = 0;↵
for (int i = 0; i < 2 * n - 1; i++) {↵
if (i >= n) {↵
dp[i] += dp[ch[i][0]] + dp[ch[i][1]];↵
}↵
if (dp[i] + cost[i] < x) {↵
dap += x - cost[i] - dp[i];↵
dp[i] = x - cost[i];↵
}↵
}↵
cout << dap << "\n";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2152H2]↵
↵
<spoiler summary="Spoiler">↵
[tutorial:2152H2]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
using lint = long long;↵
using pi = array<lint, 2>;↵
#define sz(v) ((int)(v).size())↵
#define all(v) (v).begin(), (v).end()↵
#define cr(v, n) (v).clear(), (v).resize(n);↵
↵
vector<int> pa;↵
↵
int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
int T; cin>>T;↵
while (T--){↵
int n;↵
cin >> n;↵
vector<array<lint, 3>> edges;↵
for (int i = 0; i < n - 1; i++) {↵
lint u, v, w;↵
cin >> u >> v >> w;↵
u--;↵
v--;↵
edges.push_back({w, u, v});↵
}↵
sort(all(edges));↵
reverse(all(edges));↵
cr(pa, 2 * n - 1);↵
vector<lint> cost(2 * n - 1);↵
vector<pi> ch(2 * n - 1);↵
iota(all(pa), 0);↵
for (int i = 0; i < n - 1; i++) {↵
int u = find(edges[i][1]);↵
int v = find(edges[i][2]);↵
pa[u] = i + n;↵
pa[v] = i + n;↵
ch[i + n] = {u, v};↵
cost[edges[i][1]] += edges[i][0];↵
cost[edges[i][2]] += edges[i][0];↵
cost[i + n] -= edges[i][0] * 2;↵
}↵
for (int i = n; i < 2 * n - 1; i++) {↵
cost[i] += cost[ch[i][0]] + cost[ch[i][1]];↵
}↵
// (point, slope increase)↵
vector<priority_queue<pi, vector<pi>, greater<pi>>> pq(n);↵
vector<int> idx(2 * n - 1);↵
iota(all(idx), 0);↵
for (int i = 0; i < 2 * n - 1; i++) {↵
if (i < n) {↵
pq[i].push({cost[i], 1});↵
continue;↵
}↵
if (sz(pq[idx[ch[i][0]]]) < sz(pq[idx[ch[i][1]]]))↵
swap(ch[i][0], ch[i][1]);↵
idx[i] = idx[ch[i][0]];↵
while (sz(pq[idx[ch[i][1]]])) {↵
auto tp = pq[idx[ch[i][1]]].top();↵
pq[idx[ch[i][1]]].pop();↵
pq[idx[i]].push(tp);↵
}↵
if (cost[i] >= pq[idx[i]].top()[0])↵
continue;↵
if (cost[i] >= lint(2e9))↵
continue;↵
lint A = 0, B = 0;↵
lint pv = -1;↵
while (sz(pq[idx[i]])) {↵
auto [point, slope] = pq[idx[i]].top();↵
pq[idx[i]].pop();↵
B += A * (point - pv);↵
pv = point;↵
A += slope;↵
// A x - A * pv + B = x - cost[i]↵
// (A - 1) x = A * pv - B - cost[i]↵
lint U = A * pv - B - cost[i];↵
lint L = A - 1;↵
// point <= U / L, so no need to dedup↵
if (L > 0) {↵
assert(point * L <= U);↵
if ((sz(pq[idx[i]]) == 0 || U < pq[idx[i]].top()[0] * L)) {↵
lint f1 = U / L - cost[i];↵
lint f2 = (U / L + 1 - pv) * A + B;↵
// (cost[i], 0) -> (U / L, f1) -> (U / L + 1, f2) -> increase w/ speed A↵
pq[idx[i]].push({cost[i], 1});↵
pq[idx[i]].push({U / L, f2 - f1 - 1});↵
pq[idx[i]].push({U / L + 1, A - (f2 - f1)});↵
break;↵
}↵
} else if (sz(pq[idx[i]]) == 0) {↵
pq[idx[i]].push({cost[i], 1});↵
break;↵
}↵
}↵
}↵
int q;↵
cin >> q;↵
vector<pi> queries(q);↵
for (int i = 0; i < q; i++) {↵
cin >> queries[i][0];↵
queries[i][1] = i;↵
}↵
sort(all(queries));↵
vector<lint> ans(q);↵
lint A = 0, B = 0, pv = -1;↵
auto T = idx[2 * n - 2];↵
for (auto &[x, i] : queries) {↵
while (sz(pq[T]) && pq[T].top()[0] <= x) {↵
auto [point, slope] = pq[T].top();↵
pq[T].pop();↵
B += A * (point - pv);↵
pv = point;↵
A += slope;↵
}↵
ans[i] = (x - pv) * A + B;↵
}↵
for (auto &v : ans)↵
cout << v << "\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
