Submission #320474

#	Time	Username	Problem	Language	Result	Execution time	Memory
320474		egas	Discharging (NOI20_discharging)	C++14	9 / 100	1141 ms	723276 KiB

Discharging

#include <bits/stdc++.h>

using namespace std;

template < typename T >

class SegmentTree {

private:

    T *Stree;

    T *Snum;

    long long n;

    T NullValue = 0;

    T combine(T a, T b) {

        return max(a,b);

    }

    void build(long long idx, long long s, long long e) {

        if (s > e)

            return;

        if (s == e) {

            Stree[idx] = Snum[s];

            return ;

        }

        long long m = ( s + e ) / 2;

        build( 2 * idx, s, m);

        build( 2 * idx + 1, m + 1, e);

        Stree[idx] = combine(Stree[2 * idx], Stree[2 * idx + 1] );

        return;

    }

    T queryUtil(long long idx, long long s, long long e, long long l, long long r) {

        if (l > e || r < s)

            return NullValue;

        if (s >= l && e <= r) {

            return Stree[idx];

        }

        long long m = ( s + e ) / 2;

        T left = queryUtil(2 * idx, s, m, l, r);

        T right = queryUtil(2 * idx + 1, m + 1, e, l, r);

        return combine(left, right );

    }

public:

    SegmentTree(vector<T> a) {

        this->n = a.size();

        Stree = new T[4 * n + 5];

        Snum = new T[n];

        for (long long i = 0; i < n; i++) {

            Snum[i] = a[i];

        }

        build(1, 0, n - 1);

    }

    T query(long long l, long long r) {

        return queryUtil(1, 0, n - 1, l - 1, r - 1);

    }

};

template < typename T >

class SegmentTree2 {

private:

    T *Stree;

    T *Snum;

    long long n;

    T NullValue;

    T combine(T a, T b) {

        for(auto x:a) {

            b[x.first]+=x.second;

        }

        return b;

    }

    void build(long long idx, long long s, long long e) {

        if (s > e)

            return;

        if (s == e) {

            Stree[idx] = Snum[s];

            return ;

        }

        long long m = ( s + e ) / 2;

        build( 2 * idx, s, m);

        build( 2 * idx + 1, m + 1, e);

        Stree[idx] = combine(Stree[2 * idx], Stree[2 * idx + 1] );

        return;

    }

    T queryUtil(long long idx, long long s, long long e, long long l, long long r) {

        if (l > e || r < s)

            return NullValue;

        if (s >= l && e <= r) {

            return Stree[idx];

        }

        long long m = ( s + e ) / 2;

        T left = queryUtil(2 * idx, s, m, l, r);

        T right = queryUtil(2 * idx + 1, m + 1, e, l, r);

        return combine(left, right );

    }

public:

    SegmentTree2(vector<long long> a) {

        this->n = a.size();

        Stree = new T[4 * n + 5];

        Snum = new T[n];

        for (long long i = 0; i < n; i++) {

            Snum[i][a[i]]++;

        }

        build(1, 0, n - 1);

    }

    T query(long long l, long long r) {

        return queryUtil(1, 0, n - 1, l - 1, r - 1);

    }

};

long long solve(long long idx,long long last,long long n,SegmentTree<long long> &ST,SegmentTree2<map<long long,long long>> &ST2) {

    if(idx>=n)return 0;

    if(last>=n) {

        return ST.query(idx+1,last+1)*(n-idx);

    }

    long long pos1 = ST.query(idx+1,last+1)*(n-idx) + solve(last+1,last+1,n,ST,ST2);

    long long pos2 = solve(idx,last+1,n,ST,ST2);

    return min(pos1,pos2);

}

int32_t main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    long long n;

    cin >> n;

    vector<long long> a(n);

    for(long long i = 0 ; i < n ; i++) {

        cin >> a[i];

    }

    SegmentTree<long long> ST(a);

    SegmentTree2<map<long long,long long>> ST2(a);

    long long res = solve(0,0,n,ST,ST2);

    cout << res << '\n';

    return 0;

}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 11
• Subtask 5: 0 / 14
• Subtask 6: 0 / 28