oj.uz

Submission #320474

# Submission time Handle Problem Language Result Execution time Memory
320474 2020-11-08T20:23:31 Z egas Discharging (NOI20_discharging) C++14
9 / 100
 1000 ms 723276 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 396 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 2284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 2284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1141 ms 723276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 396 KB Output is correct
15 Execution timed out 1074 ms 2284 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 396 KB Output is correct
15 Execution timed out 1074 ms 2284 KB Time limit exceeded
16 Halted 0 ms 0 KB -