Submission #1093300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093300		muhammad	Feast (NOI19_feast)	C++17	4 / 100	559 ms	262144 KiB

feast

#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 (stderr)

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 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29