Submission #913031

#	Time	Username	Problem	Language	Result	Execution time	Memory
913031		JoseSoto	Feast (NOI19_feast)	C++14	0 / 100	1067 ms	31640 KiB

feast

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(x) ((int) (x).size())
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vp = vector<pii>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vb = vector<bool>;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p){return os << '(' << p.fi << ", " << p.se << ')';}
template<typename C, typename T = typename enable_if<!is_same<C, string>::value, typename C::value_type>::type>
ostream& operator<<(ostream &os, const C &v){string sep; for(const T &x : v) os << sep << x, sep = " "; return os;}
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values){
    cout << "[Debug]\n\t" << vars << " = ";
    string d = "[";
    (..., (cout << d << values, d = "] ["));
    cout << "]\n";
}

struct ST{
    int n;
    vi st, lzy;
    ST(int n){
        this->n = n;
        st.resize(4*n + 1);
        lzy.resize(4*n + 1);
    }

    void push(int l, int r, int nd){
        if(!lzy[nd]) return;
        st[nd] += lzy[nd]*(r - l + 1);
        if(leftCh(nd) < sz(lzy)) lzy[ leftCh(nd) ] += lzy[nd];
        if(rightCh(nd) < sz(lzy)) lzy[ rightCh(nd) ] += lzy[nd];
        lzy[nd] = 0;
    }

    void add(int l, int r, int L, int R, int x, int nd){
        if(R<l || L>r) return;
        if(L <= l && r <= R){
            lzy[nd] += x;
            push(l, r, nd);
            return;
        }

        add(l, mid(l, r), L, R, x, leftCh(nd));
        add(mid(l,r)+1, r, L, R, x, rightCh(nd));

        st[nd] = st[leftCh(nd)] + st[rightCh(nd)];
        return;
    }

    void add(int l, int r, int x){
        add(1, n, l, r, x, 1);
        return;
    }

    int qry(int l, int r, int L, int R, int nd){
        push(l, r, nd);
        if(L > r || R < l) return 0;
        if(L <= l && r <= R) return st[nd];
        return qry(l, mid(l, r), L, R, leftCh(nd)) + qry(mid(l, r) + 1, r, L, R, rightCh(nd));
    }

    int qry(int l, int r){
        return qry(1, n, l, r, 1);
    }

private:
    constexpr inline int mid(const int l, const int r){ return (l+r)/2; }
    constexpr inline int leftCh(int nd){ return nd+nd; }
    constexpr inline int rightCh(int nd){ return nd+nd+1; }
};


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

    int n,k;
    cin >> n >> k;
    vl a(n + 3), b(n + 3), c(n + 3);
    ll sum = 0, maxi = 0, pos = 0;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }



    for(int i=1; i<=n; i++){
        sum += a[i];
        b[i] = sum - maxi;
        c[i] = pos;
        if(sum > maxi) maxi = sum, pos = i;
    }

    auto fn = [&](ll x){
        priority_queue< array<ll,3> > pq;
        for(int i=1; i<=n; i++) pq.push({-b[i], c[i], i});

        ST st(n);

        while(!pq.empty() && pq.top()[0] > x){
            auto val = pq.top();
            pq.pop();
            if(st.qry(val[1] + 1,val[2]) == 0){
                st.add(val[1]+1, val[2], 1);
            }
        }

        vi lol(n + 1);
        for(int i=1; i<=n; i++) lol[i] = st.qry(i, i);

        int cnt = 0;
        for(int i=1; i<=n; i++){
            if(lol[i]) continue;
            cnt++;
            int j = i;
            while(j + 1 <= n && !lol[j+1]) j++;
            i = j;
        }

        return cnt;
    };

    ll ini = 0, fin = 1e15, med;
    while(ini < fin){
        med = (ini + fin)/2;
        if(fn(med) > k) ini = med + 1;
        else fin = med;
    }


    priority_queue< array<ll,3> > pq;
    for(int i=1; i<=n; i++) pq.push({-b[i], c[i], i});

    ST st(n);

    while(!pq.empty() && pq.top()[0] > ini){
        auto val = pq.top();
        pq.pop();
        if(st.qry(val[1] + 1,val[2]) == 0){
            st.add(val[1]+1, val[2], 1);
        }
    }

    vi lol(n + 1);
    for(int i=1; i<=n; i++) lol[i] = st.qry(i, i);

    ll ans = 0;
    int cnt = 0;
    for(int i=1; i<=n; i++){
        if(lol[i]) continue;
        ll temp = 0;
        int j = i;
        while(j <= n){
            if(lol[j]) break;
            temp += a[j];
            if(temp < 0) temp = 0;
            j++;
        }
        ans += temp;
        i = j;
    }

    cout << ans << "\n";

    return 0;
}

Compilation message (stderr)

feast.cpp: In function 'void logger(std::string, Args&& ...)':
feast.cpp:27:42: warning: fold-expressions only available with '-std=c++17' or '-std=gnu++17'
   27 |     (..., (cout << d << values, d = "] ["));
      |                                          ^
feast.cpp: In function 'int main()':
feast.cpp:161:9: warning: unused variable 'cnt' [-Wunused-variable]
  161 |     int cnt = 0;
      |         ^~~

• Subtask 1: 0 / 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