Language: C++

/*
    author:  Maksim1744
    created: 13.06.2020 15:29:39
*/
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")
#pragma GCC target("sse2")
#pragma GCC target("sse3")
#pragma GCC target("sse4.1")
#pragma GCC target("sse4.2")
#pragma GCC target("popcnt")
#pragma GCC target("abm")
#pragma GCC target("mmx")
#pragma GCC target("tune=native")
#include <bits/stdc++.h>

using namespace std;

#define ll   long long
#define ld   long double

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T>& v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T>& v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T>& v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>& v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>& p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define TAG_LENGTH       25
#define LR_LEFT          left
#define LR_RIGHT         right
#define LR_VALUE         value
#define LR_SECOND_VALUE  mn
#include "C:/C++ libs/print.cpp"
const int H = 2;
#else
#define showl            42;
#define shows            42;
#define show(...)        42;
#define showm(...)       42;
#define showt(...)       42;
#define printTree(...)   42;
#define printGraph(...)  42;
#define printLRTree(...) 42;
#define printMatrix(...) 42;
#define printWGraph(...) 42;
#define debug     if (false)
const int H = 10;
#endif

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n;
    cin >> n;
    vector<int> v(n + 1), w(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> v[i] >> w[i];
    }

    vector<int> h(n + 1);
    h[1] = 1;
    for (int i = 2; i <= n; ++i)
        h[i] = h[i / 2] + 1;
    vector<map<int, int>> prepos(n + 1);
    vector<vector<pair<int, int>>> pos(n + 1);
    prepos[1][0] = 0;
    prepos[1][w[1]] = v[1];
    for (int i = 2; i <= n && h[i] <= H; ++i) {
        prepos[i] = prepos[i / 2];
        for (auto wwvv : prepos[i / 2]) {
            int ww, vv;
            tie(ww, vv) = wwvv;
            prepos[i][ww + w[i]] = max(prepos[i][ww + w[i]], vv + v[i]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        pos[i] = vector<pair<int, int>>(prepos[i].begin(), prepos[i].end());
        for (int j = 1; j < pos[i].size(); ++j)
            pos[i][j].second = max(pos[i][j].second, pos[i][j - 1].second);
    }

    // if (n == 15) {
    //     show(pos[1]);
    //     show(pos[2]);
    //     show(pos[4]);
    //     show(pos[9]);
    // }

    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int u, L;
        cin >> u >> L;
        if (h[u] <= H) {
            int ind = lowb(pos[u], make_pair(L, -1));
            if (ind == pos[u].size() || pos[u][ind].first > L) --ind;
            cout << pos[u][ind].second << '\n';
            continue;
        }
        vector<pair<int, int>> vars;
        int x = u;
        while (h[x] > H) {
            vars.eb(w[x], v[x]);
            x /= 2;
        }
        map<int, int> mm;
        for (int i = 0; i < (1 << vars.size()); ++i) {
            int ww = 0, vv = 0;
            for (int j = 0; j < vars.size(); ++j) {
                if ((i >> j) & 1) {
                    ww += vars[j].first;
                    vv += vars[j].second;
                }
            }
            mm[ww] = max(mm[ww], vv);
        }
        vector<pair<int, int>> vv(mm.begin(), mm.end());
        for (int j = 1; j < vv.size(); ++j)
            vv[j].second = max(vv[j].second, vv[j - 1].second);
        int ans = 0;
        int ind = pos[x].size() - 1;
        for (auto wv : vv) {
            int w, v;
            tie(w, v) = wv;
            if (w > L) break;
            while (ind == pos[x].size() || pos[x][ind].first > L - w) --ind;
            ans = max(ans, pos[x][ind].second + v);
        }
        cout << ans << '\n';
    }

    return 0;
}


Compiler output:
a.cc:12:41: warning: bad option '-ffunction-sections' to pragma 'optimize' [-Wpragmas]
   12 | #pragma GCC optimize("function-sections")
      |                                         ^
a.cc:13:37: warning: bad option '-fdata-sections' to pragma 'optimize' [-Wpragmas]
   13 | #pragma GCC optimize("data-sections")
      |                                     ^
a.cc:14:51: warning: bad option '-fbranch-target-load-optimize' to pragma 'optimize' [-Wpragmas]
   14 | #pragma GCC optimize("branch-target-load-optimize")
      |                                                   ^
a.cc:15:52: warning: bad option '-fbranch-target-load-optimize2' to pragma 'optimize' [-Wpragmas]
   15 | #pragma GCC optimize("branch-target-load-optimize2")
      |                                                    ^
a.cc:16:40: warning: bad option '-fbtr-bb-exclusive' to pragma 'optimize' [-Wpragmas]
   16 | #pragma GCC optimize("btr-bb-exclusive")
      |                                        ^
a.cc:44:80: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
   44 | template<typename T>             vector<T>& operator--            (vector<T>& v){for (auto& i : v) --i;            return  v;}
      |                                                                                ^
a.cc:44:80: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
a.cc:44:80: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
a.cc:44:80: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
a.cc:44:80: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
a.cc:45:80: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
   45 | template<typename T>             vector<T>& operator++            (vector<T>& v){for (auto& i : v) ++i;            return  v;}
      |                                                                                ^
a.cc:45:80: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
a.cc:45:80: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
a.cc:45:80: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
a.cc:45:80: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
a.cc:46:80: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
   46 | template<typename T>             istream& operator>>(istream& is,  vector<T>& v){for (auto& i : v) is >> i;        return is;}
      |                                                                                ^
a.cc:46:80: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
a.cc:46:80: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
a.cc:46:80: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
a.cc:46:80: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
a.cc:47:80: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
   47 | template<typename T>             ostream& operator<<(ostream& os,  vector<T>& v){for (auto& i : v) os << i << ' '; return os;}
      |                                                                                ^
a.cc:47:80: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
a.cc:47:80: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
a.cc:47:80: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
a.cc:47:80: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
a.cc:48:80: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
   48 | template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p){is >> p.first >> p.second;        return is;}
      |                                                                                ^
a.cc:48:80: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
a.cc:48:80: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
a.cc:48:80: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
a.cc:48:80: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
a.cc:49:80: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
   49 | template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>& p){os << p.first << ' ' << p.second; return os;}
      |                                                                                ^
a.cc:49:80: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
a.cc:49:80: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
a.cc:49:80: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
a.cc:49:80: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
a.cc:50:78: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
   50 | template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
      |                                                                              ^
a.cc:50:78: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
a.cc:50:78: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
a.cc:50:78: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
a.cc:50:78: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
a.cc:51:78: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
   51 | template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
      |                                                                              ^
a.cc:51:78: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
a.cc:51:78: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
a.cc:51:78: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
a.cc:51:78: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
a.cc:52:53: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
   52 | template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
      |                                                     ^
a.cc:52:53: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
a.cc:52:53: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
a.cc:52:53: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
a.cc:52:53: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
a.cc:53:53: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
   53 | template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}
      |                                                     ^
a.cc:53:53: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
a.cc:53:53: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
a.cc:53:53: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
a.cc:53:53: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
a.cc:78:10: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
   78 | int main() {
      |          ^
a.cc:78:10: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
a.cc:78:10: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
a.cc:78:10: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
a.cc:78:10: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
In file included from /usr/include/c++/14/string:43,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:25:
/usr/include/c++/14/bits/allocator.h: In destructor 'std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()':
/usr/include/c++/14/bits/allocator.h:182:7: error: inlining failed in call to 'always_inline' 'std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]': target specific option mismatch
  182 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/14/vector:66,
                 from /usr/include/c++/14/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:53:
/usr/include/c++/14/bits/stl_vector.h:132:14: note: called from here
  132 |       struct _Vector_impl
      |              ^~~~~~~~~~~~