Submission #891646

#	Time	Username	Problem	Language	Result	Execution time	Memory
891646		vjudge1	Meetings (IOI18_meetings)	C++17	36 / 100	693 ms	18072 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

vll solve(vector<int> V, int delta, int len) {
    stack<int> S;
    vll re;
    ll cur = 0;
    for(int i = 0; i < len; ++i) {
        while(!S.empty() && V[i + delta] > V[S.top() + delta]) {
            int p = S.top();
            S.pop();
            int p2 = 0;
            if(!S.empty()) p2 = S.top() + 1;
            cur -= 1ll * (p - p2 + 1) * V[p + delta];
        }
        int p = 0;
        if(!S.empty()) p = S.top() + 1;
        cur += 1ll * (i - p + 1) * V[i + delta];
        S.push(i);
        re.push_back(cur);
    }
    return re;
}

using ii = pair<int, int>;

struct banda {
    bool mono;
    int len;

    int vma = 0;

    ii st, dr; /// perechi (val, len)
    
    banda(int l = 0, int cul = 0) {
        mono = 1;
        len = l;
        st = dr = {cul, l};
        if(cul == 1) vma = l;
    }
    banda operator+(banda rhs) {
        banda re;
        if(mono && rhs.mono && st.first == rhs.st.first) {
            re = banda(len + rhs.len, st.first);
            return re;
        }
        
        re.vma = max(vma, rhs.vma);
        re.st = st;
        re.dr = rhs.dr;
        if(mono && rhs.st.first == st.first) {
            re.st.second += rhs.st.second;
        }

        if(dr.first == 1 && rhs.st.first == 1)
            re.vma = max(re.vma, dr.second + rhs.st.second);

        if(rhs.mono && dr.first == rhs.st.first)
            re.dr.second += dr.second;
        
        if(re.st.first == 1)
            re.vma = max(re.vma, re.st.second);
        if(re.dr.first == 1)
            re.vma = max(re.vma, re.dr.second);
        re.mono = 0;

        return re;
    }

};

struct AINT {
    vector<banda> V;
    int n;
    AINT(int N) : n(N), V(4 * N) {}

    void update(int u, int v) { update(u, v, 1, 0, n - 1); }

    void update(int p, int v, int u, int s, int d) {
        if(d < p || p < s) return;
        if(s == d) {
           V[u] = banda(1, v); 
           return;
        }
        update(p, v, u << 1, s, (s + d) >> 1);
        update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        V[u] = V[u << 1] + V[u << 1 | 1];
    }

    banda query(int l, int r) { return query(l, r, 1, 0, n - 1); }

    banda query(int l, int r, int u, int s, int d) {
        int m = (s + d) >> 1;
        if(l <= s && d <= r) return V[u];
        if(r <= m) return query(l, r, u << 1, s, m);
        if(m < l) return query(l, r, u << 1 | 1, m + 1, d);
        return query(l, r, u << 1, s, m) + query(l, r, u << 1 | 1, m + 1, d);
    }
};

vll minimum_costs(vi H, vi L, vi R) {
    vector<int> S(H);
    vi RH = H;
    reverse(RH.begin(), RH.end());
    vi RS(RH);
    int n = H.size();
    vll RE;
    if(H.size() <= 5000 && L.size() <= 5000) {
        for(int q = 0; q < L.size(); ++q) {
            vll opt1 = solve(S, L[q], R[q] - L[q] + 1);
            vll opt2 = solve(RS, n - 1 - R[q], R[q] - L[q] + 1);
            reverse(opt2.begin(), opt2.end());
            ll re = opt1[0] + opt2[0];
            for(int i = 0; i < R[q] - L[q] + 1; i++)
                re = min(re, opt1[i] + opt2[i] - H[i + L[q]]);
            RE.push_back(re);
        }
        return RE;
    }
    ///sper ca 0 sau 1;
    AINT A(n);
    for(int i = 0; i < n; ++i)
        A.update(i, H[i]);
    vll Re;
    int q = L.size();
    for(int i = 0; i < q; ++i) {
        int v = A.query(L[i], R[i]).vma;
        Re.push_back((R[i] - L[i] + 1) * 2 - v);
        // cout << v << " ";
    }
//    cout << "\n\n";
    return Re;
}

Compilation message (stderr)

meetings.cpp: In constructor 'AINT::AINT(int)':
meetings.cpp:80:9: warning: 'AINT::n' will be initialized after [-Wreorder]
   80 |     int n;
      |         ^
meetings.cpp:79:19: warning:   'std::vector<banda> AINT::V' [-Wreorder]
   79 |     vector<banda> V;
      |                   ^
meetings.cpp:81:5: warning:   when initialized here [-Wreorder]
   81 |     AINT(int N) : n(N), V(4 * N) {}
      |     ^~~~
meetings.cpp: In function 'vll minimum_costs(vi, vi, vi)':
meetings.cpp:115:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for(int q = 0; q < L.size(); ++q) {
      |                        ~~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40