/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 328.0 KiB
#2 Wrong Answer 20ms 736.0 KiB
#3 Wrong Answer 30ms 588.0 KiB

Code

#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

//o-set
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//debugging tool
template<typename T>
void debug(string name, T value) {
    cerr << name << " = " << value << endl;
}

template<typename T, typename U>
void debug(string name, pair<T, U> value) {
    cerr << name << " = {" << value.first << ", " << value.second << "}" << endl;
}

template<typename T>
void debug(string name, vector<T> v) {
    cerr << name << " =[ ";
    for (size_t i = 0; i < v.size(); i++) {
        if (i) {
            cerr << ", ";
        }
        cerr << v[i];
    }

    cerr << "]" << endl;
}

template<typename T>
void debug(string name, set<T> v) {
    cerr << name << " =[ ";
    for (auto it = v.begin(); it != v.end(); it++) {
        if (it != v.begin()) {
            cerr << ", ";
        }
        cerr << *it;
    }

    cerr << "]" << endl;
}



template<typename T, typename U>
void debug(string name, map<T, U> v) {
    cerr << name << " =[ ";
    for (auto it = v.begin(); it != v.end(); it++) {
        if (it != v.begin()) {
            cerr << ", ";
        }
        cerr << it->first << ": " << it->second;
    }

    cerr << "]" << endl;
}

#define DEBUG(x)        debug(#x, x);

#define int             long long
#define endl            "\n"
#define rep(i, a, b)    for (int i = a; i < b; i++)
#define fr(i, a, b)    for (int i = a; i <= b; i++)

typedef vector<int>     vi;
#define inf             1e18







class SegmentTree {
#define lc      (n << 1)
#define rc      ((n << 1) | 1)

public:
    vi a, tr;
    SegmentTree (vi aa) {
        int sz = aa.size() - 1;
        this->a = aa;
        tr.resize((sz << 2) + 3);
    }

    inline void pull(int n) {
        tr[n] = min(tr[lc], tr[rc]);
    }

    void build (int n, int b, int e)  {
        if (b == e) {
            tr[n] = a[b];
            return;
        }
        int mid = (b + e) >> 1;
        build(lc, b, mid);
        build(rc, mid + 1, e);
        pull(n);
    }

    int query (int n, int b, int e, int i, int j) {
        if (j < b or i > e) return inf;
        if (i <= b and j >= e) return tr[n];
        int mid = (b + e) >> 1;
        int l = query(lc, b, mid, i, j), r = query(rc, mid + 1, e, i, j);


        return min(l, r);
    }
};



class SegmentTreeMx {
#define lc      (n << 1)
#define rc      ((n << 1) | 1)

public:
    vi a, tr;
    SegmentTreeMx (vi aa) {
        int sz = aa.size() - 1;
        this->a = aa;
        tr.resize((sz << 2) + 3);
    }

    inline void pull(int n) {
        tr[n] = max(tr[lc], tr[rc]);
    }

    void build (int n, int b, int e)  {
        if (b == e) {
            tr[n] = a[b];
            return;
        }
        int mid = (b + e) >> 1;
        build(lc, b, mid);
        build(rc, mid + 1, e);
        pull(n);
    }

    int query (int n, int b, int e, int i, int j) {
        if (j < b or i > e) return -inf;
        if (i <= b and j >= e) return tr[n];
        int mid = (b + e) >> 1;
        int l = query(lc, b, mid, i, j), r = query(rc, mid + 1, e, i, j);


        return max(l, r);
    }
};






void solve() {
    int n, k;                       cin >> n >> k;

    vi a(n + 1), pf(n + 1);
    fr (i, 1, n)                    cin >> a[i], pf[i] = pf[i - 1 ] + a[i];

    SegmentTree sgtreeMn(a);
    sgtreeMn.build(1, 1, n);
    SegmentTreeMx sgtreeMx(a);

    sgtreeMx.build(1, 1, n);
    // DEBUG(sgtreeMx.query(1, 1, n, 1, n));

    int ans = inf;

    fr (i, 1, n - k + 1) {
        int l = i, r = i + k - 1;
        int sum = pf[r] - pf[l - 1];
        // DEBUG(i);
        // DEBUG(sum);
        int mxRange = sgtreeMx.query(1, 1, n, l, r);

        // DEBUG(mxRange);

        int mn1 = sgtreeMn.query(1, 1, n, 1, i - 1), mn2 = sgtreeMn.query(1, 1, n, r + 1, n);
        // DEBUG(mn1);
        // DEBUG(mn2);
        // if (mn1 == inf) mn1 = 0;
        // if (mn2 == inf) mn2 = 0;
        int vloMn = min(mn1, mn2);

        sum -= mxRange, sum += vloMn;
        ans = min(ans, sum);
    }

    cout << ans << '\n';
}



signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);

    int tt;     cin >> tt;
    
    while (tt--) 
        solve();
    
}

Information

Submit By
Type
Submission
Problem
P1149 Swap and Minimize
Contest
LU IUJPC : Sylhet Division 2024
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-09 06:12:10
Judged At
2024-12-09 06:12:10
Judged By
Score
1
Total Time
30ms
Peak Memory
736.0 KiB