Submission #1085285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085285		vladilius	모임들 (IOI18_meetings)	C++17	60 / 100	4672 ms	786432 KiB

meetings

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
const ll inf = 1e18;
const int N = 7.5e5;

struct DS{
    struct line{
        ll k, b;
        ll operator ()(ll x){
            return k * x + b;
        }
        line(ll ks, ll bs){
            k = ks; b = bs;
        }
    };
    vector<line> t;
    vector<pil> p;
    int n;
    DS(int ns){
        n = ns;
        t.assign(4 * n, {0, inf});
        p.resize(4 * n);
    }
    void apply(int v, pil x){
        t[v].k += x.ff; t[v].b += x.ss;
        p[v].ff += x.ff; p[v].ss += x.ss;
    }
    void push1(int& v, int& tl, int& tr){
        int vv = 2 * v;
        apply(vv, p[v]); 
        apply(vv + 1, p[v]);
        p[v] = {0, 0};
    }
    void insert(int v, int tl, int tr, line f){
        if (tl == tr){
            if (t[v](tl) > f(tl)) t[v] = f;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push1(v, tl, tr);
        if (t[v].k > f.k) swap(t[v], f);
        if (f(tm) <= t[v](tm)){
            swap(t[v], f);
            insert(vv + 1, tm + 1, tr, f);
        }
        else {
            insert(vv, tl, tm, f);
        }
    }
    void chmin(int v, int tl, int tr, int& l, int& r, line& f){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            insert(v, tl, tr, f);
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push1(v, tl, tr);
        chmin(vv, tl, tm, l, r, f);
        chmin(vv + 1, tm + 1, tr, l, r, f);
    }
    void chmin(int l, int r, int k, ll b){
        line f(k, b);
        chmin(1, 1, n, l, r, f);
    }
    void add(int v, int tl, int tr, int& l, int& r, line& f){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            apply(v, {f.k, f.b});
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push1(v, tl, tr);
        add(vv, tl, tm, l, r, f);
        add(vv + 1, tm + 1, tr, l, r, f);
    }
    void add(int l, int r, int k, ll b){
        line f(k, b);
        add(1, 1, n, l, r, f);
    }
    ll get(int v, int tl, int tr, int& x){
        if (tl == tr) return t[v](x);
        int tm = (tl + tr) / 2, vv = 2 * v;
        push1(v, tl, tr);
        if (x <= tm){
            return min(t[v](x), get(vv, tl, tm, x));
        }
        return min(t[v](x), get(vv + 1, tm + 1, tr, x));
    }
    ll get(int x){
        return get(1, 1, n, x);
    }
};

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
    const int A = 1e9;

    int n = (int) H.size(), q = (int) L.size();
    vector<int> h(n + 1), aa;
    for (int i = 1; i <= n; i++){
        h[i] = H[i - 1];
        aa.pb(h[i]);
    }
    
    sort(aa.begin(), aa.end());
    vector<int> vv;
    int i = 0;
    while (i < n){
        int j = i;
        while (j < n && aa[i] == aa[j]){
            j++;
        }
        vv.pb(aa[i]);
        i = j;
    }
    
    vector<int> :: iterator it;
    auto pos = [&](int x){
        it = lower_bound(vv.begin(), vv.end(), x);
        int j = (int) (it - vv.begin());
        return j;
    };
    
    vector<int> d[(int) vv.size()];
    for (int i = 1; i <= n; i++){
        d[pos(h[i])].pb(i);
    }
    
    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>> pw(n + 1, vector<int>(lg + 1)), pw1(n + 1, vector<int>(lg + 1, A));
    for (int i = 1; i <= n; i++) pw[i][0] = pw1[i][0] = h[i];
    for (int j = 1; j <= lg; j++){
        for (int i = 1; i + (1 << j) <= n + 1; i++){
            pw[i][j] = max(pw[i][j - 1], pw[i + (1 << (j - 1))][j - 1]);
            pw1[i][j] = min(pw1[i][j - 1], pw1[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    auto get = [&](int l, int r){
        int k = log[r - l + 1];
        return max(pw[l][k], pw[r - (1 << k) + 1][k]);
    };
    
    auto getm = [&](int l, int r){
        int k = log[r - l + 1];
        return min(pw1[l][k], pw1[r - (1 << k) + 1][k]);
    };
    
    int f[n + 1], fs = 0;
    auto pp = [&](int x, int l, int r){
        fs = 0;
        int X = pos(x);
        it = lower_bound(d[X].begin(), d[X].end(), l);
        while (it != d[X].end() && (*it) <= r){
            f[fs++] = (*it);
            it++;
        }
    };
    
    pii all1[n + 1]; int s1 = 0;
    auto gp = [&](int x, int l, int r){
        pp(x, l, r);
        s1 = 0;
        int pre = l;
        for (int j = 0; j < fs; j++){
            int i = f[j];
            if (pre < i){
                all1[s1++] = {pre, i - 1};
            }
            pre = i + 1;
        }
        if (pre <= r) all1[s1++] = {pre, r};
    };
    
    vector<pii> mp[(int) vv.size()];
    function<void(int, int)> build1 = [&](int l, int r){
        int m = get(l, r);
        mp[pos(m)].pb({l, r});
        
        gp(m, l, r);
        vector<pii> all(s1);
        for (int i = 0; i < s1; i++) all[i] = all1[i];
        
        for (auto [l1, r1]: all){
            build1(l1, r1);
        }
    };
    build1(1, n);
    
    vector<ll> out(q + 1);
    map<pii, vector<arr3>> qs;
    for (int i = 1; i <= q; i++){
        int l, r;
        l = L[i - 1]; r = R[i - 1];
        l++; r++;
        
        if (get(l, r) == getm(l, r)){
            out[i] = 1LL * h[l] * (r - l + 1);
            continue;
        }
        int k = pos(get(l, r)), l1 = 0, r1 = (int) mp[k].size() - 1;
        while (l1 + 1 < r1){
            int m = (l1 + r1) / 2;
            if (mp[k][m].ff <= l){
                l1 = m;
            }
            else {
                r1 = m - 1;
            }
        }
        if (mp[k][r1].ff <= l) l1 = r1;
        
        qs[mp[k][l1]].pb({l, r, i});
    }

    DS T1(n), T2(n);
    for (int i = 1; i <= n; i++){
        T1.add(i, i, 0, -inf);
        T2.add(i, i, 0, -inf);
    }
    vector<int> :: iterator it1, it2;
    function<void(int, int)> build = [&](int l, int r){
        int m = get(l, r);

        gp(m, l, r);
        vector<pii> all(s1);
        for (int i = 0; i < s1; i++) all[i] = all1[i];
        
        for (auto [l1, r1]: all) build(l1, r1);
        
        if (all.empty()){
            T1.add(l, r, m, -1LL * m * (l - 1));
            T2.add(l, r, -m, 1LL * m * (r + 1));
        }
                
        for (auto [l1, r1]: all){
            int m1 = get(l1, r1);
            gp(m1, l1, r1);
            ll mn = inf;
            for (int i = 0; i < s1; i++){
                // f(l1, i) = min(mn + m1 * (i - l1), f(l2, i) + m1 * (l2 - l1));
                auto [l2, r2] = all1[i];
                ll F = T1.get(r2);
                T1.add(l2, r2, 0, 1LL * m1 * (l2 - l1));

                if (mn != inf) T1.chmin(l2, r2, m1, mn - 1LL * m1 * l1);
                
                mn = min(mn, F - 1LL * m1 * (r2 - l2));
            }
            
            mn = inf;
            for (int i = s1 - 1; i >= 0; i--){
                // f(i, r1) = min(mn + m1 * (r1 - i), f(i, r2) + m1 * (r1 - r2));
                auto [l2, r2] = all1[i];
                ll F = T2.get(l2);
                T2.add(l2, r2, 0, 1LL * m1 * (r1 - r2));
                
                if (mn != inf) T2.chmin(l2, r2, -m1, mn + 1LL * m1 * r1);
                
                mn = min(mn, F - 1LL * m1 * (r2 - l2));
            }
            
            for (int j = 0; j < fs; j++){
                int i = f[j];
                ll mn = 1LL * m1 * (i - l1 + 1);
                if (i > l1) mn = min(mn, T1.get(i - 1) + m1);
                T1.add(i, i, 0, mn - T1.get(i));
            }
            for (int j = fs - 1; j >= 0; j--){
                int i = f[j];
                ll mn = 1LL * m1 * (r1 - i + 1);
                if (i < r1) mn = min(mn, T2.get(i + 1) + m1);
                T2.add(i, i, 0, mn - T2.get(i));
            }
        }
        
        if (all.empty()) return;
        
        vector<int> x1, y1;
        for (auto [l1, r1]: all){
            x1.pb(l1); y1.pb(r1);
        }
        int N = (int) all.size(), LG = log2(N);
        vector<vector<ll>> sp(N + 1, vector<ll>(LG + 1, inf));
        for (int i = 1; i <= N; i++) sp[i][0] = (T1.get(all[i - 1].ss) - 1LL * m * (all[i - 1].ss - all[i - 1].ff));
        for (int j = 1; j <= LG; j++){
            for (int i = 1; i + (1 << j) <= N + 1; i++){
                sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
            }
        }
        
        auto gets = [&](int l, int r){
            if (l > r) return inf;
            int k = log[r - l + 1];
            return min(sp[l][k], sp[r - (1 << k) + 1][k]);
        };
        
        for (auto [ql, qr, i]: qs[{l, r}]){
            it1 = lower_bound(x1.begin(), x1.end(), ql);
            it2 = upper_bound(y1.begin(), y1.end(), qr); it2--;
            
            int i1 = (int) (it1 - x1.begin()), i2 = (int) (it2 - y1.begin());
            out[i] = gets(i1 + 1, i2 + 1);
            if (out[i] != inf) out[i] += 1LL * m * (qr - ql);
            
            if (i1 > 0){
                i1--;
                if (all[i1].ss >= ql){
                    out[i] = min(out[i], T2.get(ql) + 1LL * m * (qr - all[i1].ss));
                }
            }
            if (i2 + 1 < all.size()){
                i2++;
                if (all[i2].ff <= qr){
                    out[i] = min(out[i], T1.get(qr) + 1LL * m * (all[i2].ff - ql));
                }
            }
        }
    };
    build(1, n);

    vector<ll> ret;
    for (int i = 1; i <= q; i++) ret.pb(out[i]);
    return ret;
}

Compilation message (stderr)

meetings.cpp: In lambda function:
meetings.cpp:324:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  324 |             if (i2 + 1 < all.size()){
      |                 ~~~~~~~^~~~~~~~~~~~

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