Submission #75560549

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int ll
#pragma GCC optimize("O3")

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

const int B = 3;
const int SQ = 500;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while(t--){
        int n,q;
        cin >> n >> q;
        vi dp(2*n+1,-(int)1e18);
        dp[0] = 0;
        int sum = 0;
        vector<vi>arr(n+1,vi(3));
        for(int i = 1; i<=n; i++){
            int x,y,z;
            cin >> x >> y >> z;
            arr[i] = {x,y,z};
        }
        auto merge = [&](vi a, vi b) -> vi {
            int l = 0; int r = 0;
            vi c;
            while(l < sz(a) && r < sz(b)){
                c.push_back({a[l] + b[r]});
                if(l + 1 < sz(a)){
                    l++;
                }
                else if(r + 1 < sz(b)){
                    r++;
                }
                else{
                    break;
                }
                int bl = l; int br = r;
                int val = a[bl] + b[br];
                for(int d = -B; d<=B; d++){
                    int nl = l + d; int nr = r - d;
                    if(nl >= 0 && nl < sz(a) && nr >= 0 && nr < sz(b) && a[nl] + b[nr] > val){
                        val = a[nl] + b[nr];
                        bl = nl; br = nr;
                    }
                }
                l = bl; r = br;
            }
            return c;
        };
        auto solve = [&](auto &&self, int l, int r) -> vi {
            if(r - l == 1){
                return arr[l];
            }
            int m = (l+r)/2;
            vi left = self(self,l,m);
            vi right = self(self,m,r);
            return merge(left,right);
        };
        vi big = {0};
        vi cur = {0};
        vector<vector<pii>>buckets(n+1);
        for(int i = 1; i<=q; i++){
            int d,b;
            cin >> d >> b;
            buckets[d].push_back({b,i});
        }
        vi ans(q+1);
        for(int i = 1; i<=n; i++){
            cur = merge(cur,arr[i]);
            if(sz(cur) >= SQ){
                big = merge(big,cur);
                cur = {0};
            }
            for(auto [b,id] : buckets[i]){
                for(int j = 0; j<sz(cur); j++){
                    int k = b - j;
                    if(k >= 0 && k < sz(big)){
                        ans[id] = max(ans[id],cur[j] + big[k]);
                    }
                }
            }
        }
        for(int i = 1; i<=q; i++){
            cout << ans[i] << '\n';
        }
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'int main()':
./Main.cpp:27:13: warning: unused variable 'sum' [-Wunused-variable]
   27 |         int sum = 0;
      |             ^~~
./Main.cpp:61:14: warning: variable 'solve' set but not used [-Wunused-but-set-variable]
   61 |         auto solve = [&](auto &&self, int l, int r) -> vi {
      |              ^~~~~

Judge Result