Submission #60804544
Source Code Expand
#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA
const int INF = LLONG_MAX >> 2;
void solve() {
int N; cin >> N;
vector<int> C(2<<N), D(2<<N);
for (int i = 1; i < (2<<N); ++i) cin >> C[i];
D = C;
for (int i = (1<<N)-1; i >= 1; --i) D[i] = min(C[i], D[i<<1] + D[i<<1|1]);
vector<vector<pii>> dis(2<<N);
auto init = [&](int now, int nL, int nR, auto &&self) -> void {
// debug(now, nL, nR);
dis[now].assign(nR - nL + 1, {INF, INF});
if (nL + 1 == nR) { dis[now][0] = {0, D[now]}, dis[now][1] = {D[now], 0}; return; }
int nM = (nL + nR) >> 1;
self(now<<1, nL, nM, self);
self(now<<1|1, nM, nR, self);
for (int i = nL; i <= nM; ++i) {
chmin(dis[now][i-nL].first, min(
dis[now<<1][i-nL].first,
D[now] + D[now<<1|1] + dis[now<<1][i-nL].second
));
chmin(dis[now][i-nL].second, min(
D[now] + dis[now<<1][i-nL].first,
D[now<<1|1] + dis[now<<1][i-nL].second
));
}
for (int i = nM; i <= nR; ++i) {
chmin(dis[now][i-nL].first, min(
D[now<<1] + dis[now<<1|1][i-nM].first,
D[now] + dis[now<<1|1][i-nM].second
));
chmin(dis[now][i-nL].second, min(
D[now] + D[now<<1] + dis[now<<1|1][i-nM].first,
dis[now<<1|1][i-nM].second
));
}
// debug(now, nL, nR, dis[now]);
};
init(1, 0, 1<<N, init);
auto query = [&](int qL, int qR, int now, int nL, int nR, auto &&self) -> int {
int ans = INF;
if (nL + 1 == nR) return ans;
if (nL <= qL and qR <= nR) {
chmin(ans, min({
dis[now][qL-nL].first + dis[now][qR-nL].first,
dis[now][qL-nL].second + dis[now][qR-nL].second,
dis[now][qL-nL].first + dis[now][qR-nL].second + D[now]
}));
}
int nM = (nL + nR) >> 1;
if (qL <= nM and nM <= qR) {
chmin(ans, dis[now<<1][qL-nL].second + dis[now<<1|1][qR-nM].first);
}
if (qR <= nM) chmin(ans, self(qL, qR, now<<1, nL, nM, self));
if (nM <= qL) chmin(ans, self(qL, qR, now<<1|1, nM, nR, self));
// debug(qL, qR, now, nL, nR);
return ans;
};
int Q; cin >> Q;
for (int q = 1; q <= Q; ++q) {
int op; cin >> op;
if (op == 1) {
int j, x; cin >> j >> x;
C[j] = x;
for (int i = (1<<N)-1; i >= 1; --i) D[i] = min(C[i], D[i<<1] + D[i<<1|1]);
init(1, 0, 1<<N, init);
}
if (op == 2) {
int s, t; cin >> s >> t;
int ans = query(s, t, 1, 0, 1<<N, query);
print(ans);
}
}
}
int32_t main() {
fastIO();
int t = 1; // cin >> t;
for (int _ = 1; _ <= t; ++_) {
// cout << "Case #" << _ << ": ";
solve();
}
return 0;
}
#else
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #include <bits/extc++.h>
// #include <tr2/dynamic_bitset>
using i64 = long long;
using i128 = __int128;
#define int i64
using f80 = long double;
using f128 = __float128;
#define double f80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;
// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())
#define popcnt(x) __builtin_popcountll(x)
// template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
// static_assert(D >= 1, "Vector dimension must be greater than zero!");
// template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {}
// };
// template <typename T> struct Vec<1, T> : vector<T> {
// Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
// };
template <typename T> ostream& operator << (ostream &os, const vector<T> &vec)
{ for (size_t i = 0; i < size(vec); ++i) { if (i) os << " "; os << vec[i]; } return os; }
#ifdef local
#define fastIO() void()
#define debug(...) \
_color.emplace_back("\u001b[31m"), \
fprintf(stderr, "%sAt [%s], line %d: (%s) = ", _color.back().c_str(), __FUNCTION__, __LINE__, #__VA_ARGS__), \
_do(__VA_ARGS__), _color.pop_back(), \
fprintf(stderr, "%s", _color.back().c_str())
#define print(...) \
fprintf(stdout, "%s", "\u001b[36m"), \
_P(__VA_ARGS__), \
fprintf(stdout, "%s", "\u001b[0m")
deque<string> _color{"\u001b[0m"};
template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>;
template <typename T> concept is_iterable = requires (T _t) { begin(_t); };
template <typename T> inline void _print_err(T &&_t);
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(tuple<U...> &_t);
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu);
inline void _do() { cerr << "\n"; }
template <typename T> inline void _do(T &&_t) { _print_err(_t), cerr << "\n"; }
template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) { _print_err(_t), cerr << ", ", _do(_u...); }
#else
#define fastIO() cin.tie(0)->sync_with_stdio(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#endif
inline void _P() { cout << "\n"; }
template <typename T> inline void _P(T &&_t) { cout << _t << "\n"; }
template <typename T, typename ...U> inline void _P(T &&_t, U &&..._u) { cout << _t << " ", _P(_u...); }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int getRand(int L, int R) {
if (L > R) swap(L, R);
return (int)(rng() % ((uint64_t)R - L + 1) + L);
}
template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }
template <typename T> void make_unique(vector<T> &vec) {
if (not is_sorted(ALL(vec))) sort(ALL(vec));
vec.erase(unique(ALL(vec)), end(vec));
}
/// below are Fast I/O and _print_err templates ///
/*
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
#include <unistd.h>
const int S = 65536;
int OP = 0;
char OB[S];
inline char RC() {
static char buf[S], *p = buf, *q = buf;
return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
}
inline int RI() {
static char c;
int a;
while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
if (c == '-') {
a = 0;
while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
}
else {
a = c ^ '0';
while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
}
return a;
}
inline void WI(int n, char c = '\n') {
static char buf[20], p;
if (n == 0) OB[OP++] = '0';
p = 0;
if (n < 0) {
OB[OP++] = '-';
while (n) buf[p++] = '0' - (n % 10), n /= 10;
}
else {
while (n) buf[p++] = '0' + (n % 10), n /= 10;
}
for (--p; p >= 0; --p) OB[OP++] = buf[p];
OB[OP++] = c;
if (OP > S-20) write(1, OB, OP), OP = 0;
}
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
*/
#ifdef local
template <typename T> inline void _print_err(T &&_t) { cerr << _t; }
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back() << "[";
for (bool _first = true; auto &_x : _t) {
if (!_first) cerr << ", ";
_print_err(_x), _first = false;
}
cerr << "]" << (_color.pop_back(), _color.back());
}
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back() << "(";
_print_err(_tu.first), cerr << ", ", _print_err(_tu.second);
cerr << ")" << (_color.pop_back(), _color.back());
return os;
}
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &) {
cerr << ")" << (_color.pop_back(), _color.back());
}
template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t) {
if (!I) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back();
}
cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) {
cerr << ")" << (_color.pop_back(), _color.back());
}
template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(tuple<U...> &_t) {
if (!I) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back();
}
cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}
#endif
#endif
/**
*
*
*
* iiiiii iiiiiiiiii iiiiiiiiiiiiii
* iiiiiiiiiiiii iiiiiii iiii iiiiiiiiiiiiiii ii iiii
* iiiiiiii iiiiiiiii iiii iiii iii iii iiiiiiiiii
* iiiiiii iiiiii iiii iiii ii iiiiiiiiii iiii iiii
* iiiiii iiiii iiii iiii iii iiii iiiiiiiiiiiiiiiii ii
* iiiiii iiiiiii iiiiiii iiiiiiii iii iiiiiiiiiiiiii iii iiii
* iiiiii iiiiiii iiiii ii iiii iiiiiiiiiii iiii iii iiii iiii iii
* iiiii iiiiiiii ii iiiii iiii iiiiiiiii iii iii iii iii ii iiii
* iiiiii iiiiiiii iiiii iiiii iiiiiiiiiiiiiiii iii iii ii iii iii iiii
* iiiii iiiiii iiii iiiiii iiiiiii iii iii iiii ii i ii iii iii
* iiiiii iiii iiiiiiiiiiiiiii iii iiii iiiii iii ii iii iii ii
* iiiii iiiiiiii iiiiiiiiii iiii iiiiiiiii ii iii ii
* iiiii iiiiii iiii iiiii iii ii ii i
* iiiiii iiiiiiii iiiii iiiii ii ii ii
* iiiii iiii iiii iiiiiiiiiiii ii
* iii iiii iiii iiiiiiii
* iiiii iiii
* iiii iiii
* iiii iiiii
* iii iiiii
* iii iiiii
* iii iiiiii
* iiiiiiiii
* iiiiii
*
*
*
**/
Submission Info
| Submission Time |
|
| Task |
C - Segment Tree |
| User |
SorahISA |
| Language |
C++ 23 (gcc 12.2) |
| Score |
30 |
| Code Size |
13794 Byte |
| Status |
WA |
| Exec Time |
6631 ms |
| Memory |
118420 KiB |
Judge Result
| Set Name |
Sample |
Small |
All |
| Score / Max Score |
0 / 0 |
30 / 30 |
0 / 70 |
| Status |
|
|
|
| Set Name |
Test Cases |
| Sample |
sample01.txt |
| Small |
partial-02-case01-03.txt, partial-02-case01-04.txt, partial-02-case01-08.txt, partial-02-case01-09.txt, partial-02-case01-13.txt, partial-02-case01-14.txt, partial-02-case02-18.txt, partial-02-case02-19.txt, partial-02-case02-23.txt, partial-02-case02-24.txt, partial-02-case03-28.txt, partial-02-case03-29.txt, partial-02-case03-33.txt, partial-02-case03-34.txt, partial-02-case04-38.txt, partial-02-case04-39.txt, partial-02-case04-43.txt, partial-02-case04-44.txt, partial-02-case05-48.txt, partial-02-case05-49.txt, partial-02-case05-53.txt, partial-02-case05-54.txt, partial-02-case05-58.txt, partial-02-case05-59.txt, partial-03-case01-63.txt, partial-03-case01-64.txt, partial-03-case01-65.txt |
| All |
all-02-case01-00.txt, all-02-case01-01.txt, all-02-case01-02.txt, all-02-case01-05.txt, all-02-case01-06.txt, all-02-case01-07.txt, all-02-case01-10.txt, all-02-case01-11.txt, all-02-case01-12.txt, all-02-case02-15.txt, all-02-case02-16.txt, all-02-case02-17.txt, all-02-case02-20.txt, all-02-case02-21.txt, all-02-case02-22.txt, all-02-case03-25.txt, all-02-case03-26.txt, all-02-case03-27.txt, all-02-case03-30.txt, all-02-case03-31.txt, all-02-case03-32.txt, all-02-case04-35.txt, all-02-case04-36.txt, all-02-case04-37.txt, all-02-case04-40.txt, all-02-case04-41.txt, all-02-case04-42.txt, all-02-case05-45.txt, all-02-case05-46.txt, all-02-case05-47.txt, all-02-case05-50.txt, all-02-case05-51.txt, all-02-case05-52.txt, all-02-case05-55.txt, all-02-case05-56.txt, all-02-case05-57.txt, all-03-case01-60.txt, all-03-case01-61.txt, all-03-case01-62.txt, partial-02-case01-03.txt, partial-02-case01-04.txt, partial-02-case01-08.txt, partial-02-case01-09.txt, partial-02-case01-13.txt, partial-02-case01-14.txt, partial-02-case02-18.txt, partial-02-case02-19.txt, partial-02-case02-23.txt, partial-02-case02-24.txt, partial-02-case03-28.txt, partial-02-case03-29.txt, partial-02-case03-33.txt, partial-02-case03-34.txt, partial-02-case04-38.txt, partial-02-case04-39.txt, partial-02-case04-43.txt, partial-02-case04-44.txt, partial-02-case05-48.txt, partial-02-case05-49.txt, partial-02-case05-53.txt, partial-02-case05-54.txt, partial-02-case05-58.txt, partial-02-case05-59.txt, partial-03-case01-63.txt, partial-03-case01-64.txt, partial-03-case01-65.txt, sample01.txt |
| Case Name |
Status |
Exec Time |
Memory |
| all-02-case01-00.txt |
WA |
26 ms |
3532 KiB |
| all-02-case01-01.txt |
WA |
26 ms |
3620 KiB |
| all-02-case01-02.txt |
WA |
28 ms |
3500 KiB |
| all-02-case01-05.txt |
WA |
36 ms |
3628 KiB |
| all-02-case01-06.txt |
WA |
36 ms |
3476 KiB |
| all-02-case01-07.txt |
WA |
36 ms |
3644 KiB |
| all-02-case01-10.txt |
WA |
60 ms |
3520 KiB |
| all-02-case01-11.txt |
WA |
56 ms |
3524 KiB |
| all-02-case01-12.txt |
WA |
48 ms |
3528 KiB |
| all-02-case02-15.txt |
WA |
417 ms |
3516 KiB |
| all-02-case02-16.txt |
WA |
769 ms |
3540 KiB |
| all-02-case02-17.txt |
WA |
126 ms |
3496 KiB |
| all-02-case02-20.txt |
WA |
419 ms |
3660 KiB |
| all-02-case02-21.txt |
WA |
739 ms |
3652 KiB |
| all-02-case02-22.txt |
WA |
927 ms |
3572 KiB |
| all-02-case03-25.txt |
TLE |
6625 ms |
6236 KiB |
| all-02-case03-26.txt |
TLE |
6622 ms |
4696 KiB |
| all-02-case03-27.txt |
WA |
4092 ms |
3844 KiB |
| all-02-case03-30.txt |
TLE |
6622 ms |
4012 KiB |
| all-02-case03-31.txt |
TLE |
6622 ms |
4052 KiB |
| all-02-case03-32.txt |
TLE |
6622 ms |
3968 KiB |
| all-02-case04-35.txt |
TLE |
6622 ms |
16148 KiB |
| all-02-case04-36.txt |
TLE |
6626 ms |
29988 KiB |
| all-02-case04-37.txt |
TLE |
6622 ms |
58764 KiB |
| all-02-case04-40.txt |
TLE |
6625 ms |
58724 KiB |
| all-02-case04-41.txt |
TLE |
6623 ms |
30048 KiB |
| all-02-case04-42.txt |
TLE |
6623 ms |
16188 KiB |
| all-02-case05-45.txt |
TLE |
6631 ms |
118420 KiB |
| all-02-case05-46.txt |
TLE |
6628 ms |
118288 KiB |
| all-02-case05-47.txt |
TLE |
6628 ms |
118264 KiB |
| all-02-case05-50.txt |
TLE |
6628 ms |
118280 KiB |
| all-02-case05-51.txt |
TLE |
6628 ms |
118252 KiB |
| all-02-case05-52.txt |
TLE |
6628 ms |
118304 KiB |
| all-02-case05-55.txt |
TLE |
6628 ms |
118264 KiB |
| all-02-case05-56.txt |
TLE |
6628 ms |
118296 KiB |
| all-02-case05-57.txt |
TLE |
6628 ms |
118292 KiB |
| all-03-case01-60.txt |
TLE |
6631 ms |
118336 KiB |
| all-03-case01-61.txt |
TLE |
6628 ms |
118272 KiB |
| all-03-case01-62.txt |
TLE |
6628 ms |
118288 KiB |
| partial-02-case01-03.txt |
AC |
29 ms |
3568 KiB |
| partial-02-case01-04.txt |
AC |
29 ms |
3640 KiB |
| partial-02-case01-08.txt |
AC |
30 ms |
3640 KiB |
| partial-02-case01-09.txt |
AC |
31 ms |
3476 KiB |
| partial-02-case01-13.txt |
AC |
31 ms |
3524 KiB |
| partial-02-case01-14.txt |
AC |
31 ms |
3572 KiB |
| partial-02-case02-18.txt |
AC |
32 ms |
3636 KiB |
| partial-02-case02-19.txt |
AC |
34 ms |
3564 KiB |
| partial-02-case02-23.txt |
AC |
33 ms |
3560 KiB |
| partial-02-case02-24.txt |
AC |
32 ms |
3640 KiB |
| partial-02-case03-28.txt |
AC |
37 ms |
4528 KiB |
| partial-02-case03-29.txt |
AC |
38 ms |
6176 KiB |
| partial-02-case03-33.txt |
AC |
37 ms |
4504 KiB |
| partial-02-case03-34.txt |
AC |
36 ms |
4528 KiB |
| partial-02-case04-38.txt |
AC |
95 ms |
58532 KiB |
| partial-02-case04-39.txt |
AC |
93 ms |
58548 KiB |
| partial-02-case04-43.txt |
AC |
52 ms |
16044 KiB |
| partial-02-case04-44.txt |
AC |
66 ms |
29804 KiB |
| partial-02-case05-48.txt |
AC |
148 ms |
118212 KiB |
| partial-02-case05-49.txt |
AC |
149 ms |
118212 KiB |
| partial-02-case05-53.txt |
AC |
150 ms |
118228 KiB |
| partial-02-case05-54.txt |
AC |
148 ms |
118216 KiB |
| partial-02-case05-58.txt |
AC |
150 ms |
118192 KiB |
| partial-02-case05-59.txt |
AC |
152 ms |
118272 KiB |
| partial-03-case01-63.txt |
AC |
153 ms |
118176 KiB |
| partial-03-case01-64.txt |
AC |
140 ms |
118192 KiB |
| partial-03-case01-65.txt |
AC |
142 ms |
118264 KiB |
| sample01.txt |
AC |
1 ms |
3516 KiB |