Submission #71645179

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i, s, e) for(int (i) = (s); (i) <= (e); ++(i))
#define _rep(i, s, e) for(int (i) = (s); (i) >= (e); --(i))
#define fep(i, s, e) for(int (i) = (s); (i) < (e); ++(i))
#define _fep(i, s, e) for(int (i) = (s); (i) > (e); --(i))

// #define int long long
#define pii pair<int, int>

using namespace std;

constexpr int inf = numeric_limits<int>::max() / 2;
constexpr int ninf = numeric_limits<int>::min() / 2;
constexpr int mod = 998244353;
constexpr double eps = 1e-9;

int n, q, val[2][19][2];

struct Segtree {
	int tr[(1 << 20) + 5], mn[(1 << 20) + 5];
	void build(int l, int r, int p) {
		if(l == r) {
			mn[p] = tr[p];
			mn[p << 1] = inf;
			mn[p << 1 | 1] = inf;
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, p << 1);
		build(mid + 1, r, p << 1 | 1);
		mn[p] = min(tr[p], mn[p << 1] + mn[p << 1 | 1]);
		return;
	}
	void update(int p, int d) {
		tr[p] = d;
		while(p) {
			mn[p] = min(tr[p], mn[p << 1] + mn[p << 1 | 1]);
			p >>= 1;
		}
		return;
	}
} tr;

void calc(int &x, int op) {
	if(x == (1 << n)) {
		x += (1 << n) - 1;
		val[op][0][0] = tr.mn[x];
		val[op][0][1] = 0;
	} else {
		x += (1 << n);
		val[op][0][0] = 0;
		val[op][0][1] = tr.mn[x];
	}
	int cur = x;
	rep(i, 1, n) {
		if(cur & 1) {
			val[op][i][0] = min(val[op][i - 1][0] + tr.mn[cur ^ 1], val[op][i - 1][1] + tr.mn[cur >> 1]);
			val[op][i][1] = val[op][i - 1][1];
		} else {
			val[op][i][0] = val[op][i - 1][0];
			val[op][i][1] = min(val[op][i - 1][1] + tr.mn[cur ^ 1], val[op][i - 1][0] + tr.mn[cur >> 1]);
		}
		cur >>= 1;
		val[op][i][0] = min(val[op][i][0], val[op][i][1] + tr.mn[cur]);
		val[op][i][1] = min(val[op][i][1], val[op][i][0] + tr.mn[cur]);
	}
	return;
}

void solve() {
	cin >> n;
	fep(i, 1, 1 << (n + 1)) {
		cin >> tr.tr[i];
	}
	tr.build(1, 1 << n, 1);
	cin >> q;
	while(q--) {
		int op, x, y, ans = inf;
		cin >> op >> x >> y;
		if(op == 1) {
			tr.update(x, y);
		} else {
			calc(x, 0);
			calc(y, 1);
			rep(i, 0, n) {
				if(x == y) {
					ans = min(ans, val[0][i][0] + val[1][i][0]);
					ans = min(ans, val[0][i][1] + val[1][i][1]);
				} else if(x + 1 == y) {
					ans = min(ans, val[0][i][1] + val[1][i][0]);
				} else if(y + 1 == x) {
					ans = min(ans, val[1][i][1] + val[0][i][0]);
				}
				x >>= 1;
				y >>= 1;
			}
			cout << ans << '\n';
		}
	}
	return;
}

signed main() {
//	freopen("bumper.in", "r", stdin);
//	freopen("bumper.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T = 1;
	while(T--) solve();
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void calc(int&, int)’:
Main.cpp:3:30: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
    3 | #define rep(i, s, e) for(int (i) = (s); (i) <= (e); ++(i))
      |                              ^~~
Main.cpp:56:9: note: in expansion of macro ‘rep’
   56 |         rep(i, 1, n) {
      |         ^~~
Main.cpp:3:30: note: remove parentheses
    3 | #define rep(i, s, e) for(int (i) = (s); (i) <= (e); ++(i))
      |                              ^~~
Main.cpp:56:9: note: in expansion of macro ‘rep’
   56 |         rep(i, 1, n) {
      |         ^~~
Main.cpp: In function ‘void solve()’:
Main.cpp:5:30: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
    5 | #define fep(i, s, e) for(int (i) = (s); (i) < (e); ++(i))
      |                              ^~~
Main.cpp:73:9: note: in expansion of macro ‘fep’
   73 |         fep(i, 1, 1 << (n + 1)) {
      |         ^~~
Main.cpp:5:30: note: remove parentheses
    5 | #define fep(i, s, e) for(int (i) = (s); (i) < (e); ++(i))
      |                              ^~~
Main.cpp:73:9: note: in expansion of macro ‘fep’
   73 |         fep(i, 1, 1 << (n + 1)) {
      |         ^~~
Main.cpp:3:30: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
    3 | #define rep(i, s, e) for(int (i) = (s); (i) <= (e); ++(i))
      |                              ^~~
Main.cpp:86:25: note: in expansion of macro ‘rep’
   86 |                         rep(i, 0, n) {
      |                         ^~~
Main.cpp:3:30: note: remove parentheses
    3 | #define rep(i, s, e) for(int (i) = (s); (i) <= (e); ++(i))
      |                              ^~~
Main.cpp:86:25: note: in expansion of macro ‘rep’
   86 |                         rep(i, 0, n) {
      |                         ^~~

Judge Result