Submission #1075070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075070		vladilius	Meetings (IOI18_meetings)	C++17	60 / 100	5554 ms	592080 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
const ll inf = numeric_limits<ll> :: max();

struct ST{
    vector<ll> t;
    int n;
    void init(int ns){
        n = ns;
        t.assign(4 * n, inf);
    }
    void upd(int v, int tl, int tr, int& p, ll& k){
        if (tl == tr){
            t[v] = k;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, k);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, k);
        }
        t[v] = min(t[vv], t[vv + 1]);
    }
    void upd(int p, ll k){
        upd(1, 1, n, p, k);
    }
    ll get(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return inf;
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) / 2, vv = 2 * v;
        return min(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r));
    }
    ll get(int l, int r){
        return get(1, 1, n, l, r);
    }
};

vector<ll> minimum_costs(vector<int> A1, vector<int> L, vector<int> R){
    int n = (int) A1.size(), q = (int) L.size();
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) a[i] = A1[i - 1];
    
    vector<int> log(n + 1);
    for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1;
    const int lg = log[n];
    vector<vector<int>> sp(n + 1, vector<int>(lg + 1));
    for (int i = 1; i <= n; i++) sp[i][0] = a[i];
    for (int j = 1; j <= lg; j++){
        for (int i = 1; i + (1 << j) <= n + 1; i++){
            sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
        }
    }

    auto get = [&](int l, int r){
        if (l > r) swap(l, r);
        int k = log[r - l + 1];
        return max(sp[l][k], sp[r - (1 << k) + 1][k]);
    };
    
    vector<ll> ret;

    map<int, vector<int>> d;
    for (int i = 1; i <= n; i++) d[a[i]].pb(i);

    vector<int> :: iterator it1, it2;
    map<pii, ll> mp;
    
    auto len = [&](int l, int r){
        return (r - l + 1);
    };
    
    map<int, ST> T;
    for (auto p: d){
        T[p.ff].init((int) p.ss.size());
    }
    
    auto f = [&](int l, int r){
        int mx = get(l, r);
        
        it1 = lower_bound(d[mx].begin(), d[mx].end(), l);
        it2 = upper_bound(d[mx].begin(), d[mx].end(), r); it2--;
        
        ll out = 1LL * mx * len(l, r);
        
        if (l < (*it1)) out = min(out, mp[{l, (*it1) - 1}] + 1LL * mx * (len(l, r) - len(l, (*it1) - 1)));
        if ((*it2) < r) out = min(out, mp[{(*it2) + 1, r}] + 1LL * mx * (len(l, r) - len((*it2) + 1, r)));
        
        int l1 = (int) (it1 - d[mx].begin()) + 1, r1 = (int) (it2 - d[mx].begin());
        if (l1 <= r1){
            out = min(out, T[mx].get(l1, r1) + 1LL * mx * len(l, r));
        }
        return out;
    };
    
    
    function<void(int, int)> build = [&](int l, int r){
        int mx = get(l, r);
        
        it1 = lower_bound(d[mx].begin(), d[mx].end(), l);
        it2 = upper_bound(d[mx].begin(), d[mx].end(), r); it2--;
        
        vector<pii> st;
        vector<arr3> all;
        if (l < (*it1)) st.pb({l, (*it1) - 1});
        for (int i = (int) (it1 - d[mx].begin()); i < (int) (it2 - d[mx].begin()); i++){
            st.pb({d[mx][i] + 1, d[mx][i + 1] - 1});
            all.pb({d[mx][i] + 1, d[mx][i + 1] - 1, i});
        }
        if ((*it2) < r) st.pb({(*it2) + 1, r});
        
        for (auto [l1, r1]: st) build(l1, r1);
        
        for (int i = 0; i < st.size(); i++){
            auto [l1, r1] = st[i];
            for (int j = l1; j <= r1; j++){
                mp[{l1, j}] = f(l1, j);
                mp[{j, r1}] = f(j, r1);
            }
        }
        
        for (auto [l1, r1, jj]: all){
            T[mx].upd(jj + 1, mp[{l1, r1}] - 1LL * mx * len(l1, r1));
        }

    };
    build(1, n);
    
    for (int i = 0; i < q; i++){
        int l, r; // cin>>l>>r;
        l = L[i]; r = R[i];
        l++; r++;

        ret.pb(f(l, r));
    }
    return ret;
}

Compilation message (stderr)

meetings.cpp: In lambda function:
meetings.cpp:122:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for (int i = 0; i < st.size(); i++){
      |                         ~~^~~~~~~~~~~

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