oj.uz

Submission #1093300

# Submission time Handle Problem Language Result Execution time Memory
1093300 2024-09-26T14:05:19 Z muhammad Feast (NOI19_feast) C++17
4 / 100
 559 ms 262144 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // For LLONG_MAX and LLONG_MIN

#define N 300000
#define H_ 19   // H_ = ceil(log2(N + 1))
#define N_ (1 << H_)
#define INF LLONG_MAX

using namespace std;

long long min_ll(long long a, long long b) { return a < b ? a : b; }
long long max_ll(long long a, long long b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
    return (X *= 3) >> 1;
}

// These vectors replace the fixed-size arrays
vector<long long> ppmn(N_ * 2, INF), ppmx(N_ * 2, -INF), ssmn(N_ * 2), ssmx(N_ * 2);
int n_;

void pull(int i) {
    int l = i << 1, r = l | 1;

    ppmn[i] = min_ll(ppmn[l], ppmn[r]);
    ppmx[i] = max_ll(ppmx[l], ppmx[r]);
    ssmn[i] = min_ll(ssmn[l], ssmn[r]);

    if (ppmx[l] != -INF && ppmn[r] != INF)
        ssmn[i] = min_ll(ssmn[i], ppmn[r] - ppmx[l]);

    ssmx[i] = max_ll(ssmx[l], ssmx[r]);
    if (ppmn[l] != INF && ppmx[r] != -INF)
        ssmx[i] = max_ll(ssmx[i], ppmx[r] - ppmn[l]);
}

void build(vector<long long>& aa, int n) {
    n_ = 1;
    while (n_ < n) n_ <<= 1;

    for (int i = 0; i < n_; i++) {
        if (i < n) {
            ppmn[n_ + i] = aa[i];
            ppmx[n_ + i] = aa[i];
        } else {
            ppmn[n_ + i] = INF;
            ppmx[n_ + i] = -INF;
        }
        ssmn[n_ + i] = ssmx[n_ + i] = 0;
    }
    for (int i = n_ - 1; i > 0; i--)
        pull(i);
}

long long query_mn(int l, int r, int& l_, int& r_) {
    vector<int> qu, qu_;
    l += n_;
    r += n_;

    while (l <= r) {
        if (l & 1) qu.push_back(l++);
        if (!(r & 1)) qu_.push_back(r--);
        l >>= 1;
        r >>= 1;
    }

    while (!qu_.empty()) {
        qu.push_back(qu_.back());
        qu_.pop_back();
    }

    long long s_ = INF;
    int hl = -1, hr = -1, hl_ = -1, hr_ = -1, l_val = -1;

    for (int hr = 0, l = -1; hr < qu.size(); ++hr) {
        int r = qu[hr];
        if (s_ > ssmn[r])
            s_ = ssmn[r], hl_ = hr_ = hr;
        if (l != -1 && s_ > ppmn[r] - ppmx[l])
            s_ = ppmn[r] - ppmx[l], hl_ = hl, hr_ = hr;
        if (ppmx[r] != -INF && (hl == -1 || ppmx[l] < ppmx[r]))
            hl = hr, l = r;
    }

    if (hl_ == hr_) {
        int i = qu[hl_];
        while (i < n_) {
            if (ssmn[i << 1] == ssmn[i]) i = i << 1;
            else if (ssmn[i << 1 | 1] == ssmn[i]) i = i << 1 | 1;
            else break;
        }
        l = r = (i >= n_) ? i : ((i << 1) | 1);
    } else {
        l = qu[hl_], r = qu[hr_];
    }

    while (l < n_) l = ppmx[l << 1] == ppmx[l] ? l << 1 : l << 1 | 1;
    while (r < n_) r = ppmn[r << 1] == ppmn[r] ? r << 1 : r << 1 | 1;

    l_ = l - n_;
    r_ = r - n_;
    return s_;
}

long long query_mx(int l, int r, int& l_, int& r_) {
    vector<int> qu, qu_;
    l += n_;
    r += n_;

    while (l <= r) {
        if (l & 1) qu.push_back(l++);
        if (!(r & 1)) qu_.push_back(r--);
        l >>= 1;
        r >>= 1;
    }

    while (!qu_.empty()) {
        qu.push_back(qu_.back());
        qu_.pop_back();
    }

    long long s_ = -INF;
    int hl = -1, hr = -1, hl_ = -1, hr_ = -1, l_val = -1;

    for (int hr = 0, l = -1; hr < qu.size(); ++hr) {
        int r = qu[hr];
        if (s_ < ssmx[r])
            s_ = ssmx[r], hl_ = hr_ = hr;
        if (l != -1 && s_ < ppmx[r] - ppmn[l])
            s_ = ppmx[r] - ppmn[l], hl_ = hl, hr_ = hr;
        if (ppmn[r] != INF && (hl == -1 || ppmn[l] > ppmn[r]))
            hl = hr, l = r;
    }

    if (hl_ == hr_) {
        int i = qu[hl_];
        while (i < n_) {
            if (ssmx[i << 1] == ssmx[i]) i = i << 1;
            else if (ssmx[i << 1 | 1] == ssmx[i]) i = i << 1 | 1;
            else break;
        }
        l = r = (i >= n_) ? i : ((i << 1) | 1);
    } else {
        l = qu[hl_], r = qu[hr_];
    }

    while (l < n_) l = ppmn[l << 1] == ppmn[l] ? l << 1 : l << 1 | 1;
    while (r < n_) r = ppmx[r << 1] == ppmx[r] ? r << 1 : r << 1 | 1;

    l_ = l - n_;
    r_ = r - n_;
    return s_;
}

void solve(int l, int r, int flip, vector<long long>& ss, int& m) {
    long long s;
    int l_, r_;

    s = !flip ? query_mx(l, r, l_, r_) : query_mn(l, r, l_, r_);
    if (s != 0) {
        ss[m++] = !flip ? s : -s;
        solve(l, l_, flip, ss, m);
        solve(l_, r_, flip ^ 1, ss, m);
        solve(r_, r, flip, ss, m);
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> aa(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        cin >> aa[i];
        aa[i] += aa[i - 1];
    }

    build(aa, n + 1);
    vector<long long> ss(N + 1);
    int m = 0;

    solve(0, n, 0, ss, m);
    sort(ss.begin(), ss.begin() + m, greater<long long>());

    long long ans = 0;
    for (int h = 0; h < k; ++h) {
        ans += ss[h];
    }

    cout << ans << endl;
    return 0;
}

Compilation message

feast.cpp: In function 'long long int query_mn(int, int, int&, int&)':
feast.cpp:79:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int hr = 0, l = -1; hr < qu.size(); ++hr) {
      |                              ~~~^~~~~~~~~~~
feast.cpp:77:18: warning: unused variable 'hr' [-Wunused-variable]
   77 |     int hl = -1, hr = -1, hl_ = -1, hr_ = -1, l_val = -1;
      |                  ^~
feast.cpp:77:47: warning: unused variable 'l_val' [-Wunused-variable]
   77 |     int hl = -1, hr = -1, hl_ = -1, hr_ = -1, l_val = -1;
      |                                               ^~~~~
feast.cpp: In function 'long long int query_mx(int, int, int&, int&)':
feast.cpp:129:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for (int hr = 0, l = -1; hr < qu.size(); ++hr) {
      |                              ~~~^~~~~~~~~~~
feast.cpp:127:18: warning: unused variable 'hr' [-Wunused-variable]
  127 |     int hl = -1, hr = -1, hl_ = -1, hr_ = -1, l_val = -1;
      |                  ^~
feast.cpp:127:47: warning: unused variable 'l_val' [-Wunused-variable]
  127 |     int hl = -1, hr = -1, hl_ = -1, hr_ = -1, l_val = -1;
      |                                               ^~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 40528 KB Output is correct
2 Correct 82 ms 40788 KB Output is correct
3 Correct 88 ms 40844 KB Output is correct
4 Correct 96 ms 40788 KB Output is correct
5 Correct 84 ms 40584 KB Output is correct
6 Correct 81 ms 40524 KB Output is correct
7 Correct 81 ms 40528 KB Output is correct
8 Correct 87 ms 40700 KB Output is correct
9 Correct 80 ms 40532 KB Output is correct
10 Correct 85 ms 40528 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 559 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 337 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 287 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 287 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 287 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 40528 KB Output is correct
2 Correct 82 ms 40788 KB Output is correct
3 Correct 88 ms 40844 KB Output is correct
4 Correct 96 ms 40788 KB Output is correct
5 Correct 84 ms 40584 KB Output is correct
6 Correct 81 ms 40524 KB Output is correct
7 Correct 81 ms 40528 KB Output is correct
8 Correct 87 ms 40700 KB Output is correct
9 Correct 80 ms 40532 KB Output is correct
10 Correct 85 ms 40528 KB Output is correct
11 Runtime error 559 ms 262144 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -