/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 3ms 788.0 KiB
#3 Accepted 1ms 576.0 KiB
#4 Accepted 33ms 3.801 MiB
#5 Accepted 29ms 3.535 MiB
#6 Accepted 39ms 3.617 MiB
#7 Accepted 2ms 532.0 KiB
#8 Accepted 39ms 11.012 MiB
#9 Accepted 42ms 11.062 MiB

Code

#include <bits/stdc++.h>     //   All praise is due to Allah alone, and peace and blessings be
using namespace std;         //         upon him, after whom there is no other Prophet.

template<class T> class SPT { vector<vector<T>> mr;
public: SPT(const vector<T>& arr){
        int n = arr.size(), k = log2(n) + 1;
        mr = vector<vector<T>>(n, vector<T>(k));
        for (int i = 0; i < n; i++) mr[i][0] = arr[i];
        for (int j = 1; j < k; j++) {
            for (int i = 0; i + (1 << j) - 1 < n; i++) {
                mr[i][j] = max(mr[i][j - 1], mr[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    T query(int L, int R) {
        int j = 31 - __builtin_clz(R - L + 1);
        return max(mr[L][j], mr[R - (1 << j) + 1][j]);
    }
};

int32_t main() {
    cin.tie(0)->sync_with_stdio(false);

    int32_t Case = 1;    cin >> Case;
    for (int T = 1; T <= Case; T++) {

        int n; cin >> n;
        int ar[n]; vector<int> br(n);
        for(int & i : ar) cin >> i;
        for(int & i : br) cin >> i;
        SPT<int> st(br);

        function<void()> Test_Case = [&]() {
            int64_t sum = 0;
            for(int i = 0; i < n; i++) {
                int val = st.query(i, n - 1);
                // cout << val << ' ';
                if(val > ar[i]) {
                    sum += val - ar[i];
                }
            }
            cout << sum << '\n';
        };
        Test_Case();
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1228 Business Strategy
Contest
LUCC Presents Intra LU Junior Programming Contest - Replay
Language
C++17 (G++ 13.2.0)
Submit At
2025-09-02 16:20:06
Judged At
2025-09-02 16:20:06
Judged By
Score
100
Total Time
42ms
Peak Memory
11.062 MiB