Submission #587478

#	Time	Username	Problem	Language	Result	Execution time	Memory
587478		definitelynotmee	Meetings (IOI18_meetings)	C++17	60 / 100	2314 ms	68856 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const int INF = 1e9;

struct SegTree{
    struct seg{
        int val = 0, lz = 0;
    };
    vector<seg> tree;
    int sz, ql, qr, qval;
    SegTree(int n = 0){
        sz = n;
        tree = vector<seg>(4*n+1);
    }
    void refresh(int id, int l, int r){
        if(tree[id].lz == 0)
            return;
        if(l!=r){
            int e = id*2+1, d = id*2+2;
            tree[e].lz+=tree[id].lz;
            tree[d].lz+=tree[id].lz;
        }
        tree[id].val+=tree[id].lz;
        tree[id].lz = 0;
    }
    void update(int id, int l, int r){
        refresh(id,l,r);
        if(l > qr || r < ql)
            return;
        if(ql <= l && r <= qr){
            tree[id].lz+=qval;
            refresh(id,l,r);
            return;
        }
        int e = id*2+1, d = id*2+2, m = (l+r)>>1;
        update(e,l,m);
        update(d,m+1,r);
        tree[id] = {max(tree[e].val,tree[d].val),0};
    }

    int query(int id, int l, int r){
        refresh(id,l,r);
        if(l > qr || r < ql)
            return 0;
        if(ql <= l && r <= qr)
            return tree[id].val;
        int e = id*2+1, d = id*2+2, m = (l+r)>>1;
        return max(query(e,l,m),query(d,m+1,r));
    }

    void makeupd(int l, int r, int val){
        ql = l, qr = r, qval = val;
        update(0,0,sz-1);
    }

    int makeqry(int l, int r){
        ql = l, qr = r;
        return query(0,0,sz-1);
    }
};

struct upd{
    int l, r, val;
};


std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    int Q = L.size();
    int n = H.size();
    if(ll(n)*Q <= 1e8){
        vector<ll> resp(Q);
        vector<ll> val(n);

        for(int q = 0; q < Q; q++){
            fill(val.begin()+L[q],val.begin()+R[q]+1,0);
            ll cur = 0;
            vector<pll> st;
            for(int i = L[q]; i <= R[q]; i++){
                ll ct = 1;
                while(!st.empty() && st.back().ff <= H[i]){
                    cur-=st.back().ff*st.back().ss;
                    ct+=st.back().ss;
                    st.pop_back();
                }
                cur+=ct*H[i];
                st.push_back({H[i],ct});
                val[i]+=cur;
            }

            st.clear();
            cur = 0;

            for(int i = R[q]; i >= L[q]; i--){
                val[i]+=cur;

                ll ct = 1;
                while(!st.empty() && st.back().ff <= H[i]){
                    cur-=st.back().ff*st.back().ss;
                    ct+=st.back().ss;
                    st.pop_back();
                }
                cur+=ct*H[i];
                st.push_back({H[i],ct});
            }

            resp[q] = *min_element(val.begin()+L[q],val.begin()+R[q]+1);
        }
        return resp;
    }

    vector<ll> resp(Q);
    vector<int> o(Q);
    iota(all(o),0);
    sort(all(o),[&](int a, int b){
        return R[a] < R[b];
    });

    for(int & i : H)
        i--;
    
    int ptr = -1;

    array<vector<pii>,20> s;

    SegTree st(n);

    for(int q = 0; q < Q; q++){
        int l = L[o[q]], r = R[o[q]];
        while(r > ptr){
            ptr++;
            for(int i = 19; i > H[ptr]; i--){
                if(s[i].empty() || s[i].back().ff != ptr-1){
                    st.makeupd(ptr,ptr,1);
                    s[i].push_back({ptr,1});
                } else {
                    int sz = s[i].back().ss;
                    st.makeupd(ptr-sz,ptr-1,-sz);
                    sz++;
                    st.makeupd(ptr-sz+1,ptr,sz);
                    s[i].pop_back();
                    s[i].push_back({ptr,sz});
                }
            }
            // cout << "r = " << ptr << ":\n";
            // for(int i = 1; i < 5; i++){
            //     cout << i << " => ";
            //     for(pii j : s[i])
            //         cout << "(" << j.ff << ',' << j.ss << ") ";
            //     cout << '\n';
            // }
            // cout << "queries: ";
            // for(int i = 0; i <= ptr; i++)
            //     cout << st.makeqry(i,i) << ' ';
            // cout << '\n';
        }
        vector<upd> undo;
        undo.reserve(20);
        for(int i = 1; i < 20; i++){
            int id = lower_bound(all(s[i]),make_pair(l,0))-s[i].begin();
            if(id == s[i].size() || s[i][id].ff-s[i][id].ss+1 >= l)
                continue;
            //cout << "undo " << l << ' ' << r << ": " << i << ' ' << s[i][id].ff << ' ' << s[i][id].ss << '\n';
            int newsz = s[i][id].ff-l+1;
            st.makeupd(l,s[i][id].ff,newsz-s[i][id].ss);
            undo.push_back({l,s[i][id].ff,-(newsz-s[i][id].ss)});
        }
        resp[o[q]] = 20*(r-l+1)-st.makeqry(l,r);
        for(upd i : undo){
            //cout << "->"<< i.l << ' ' << i.r << ' ' << -i.val << '\n';
            st.makeupd(i.l,i.r,i.val);
        }
    }
    
    return resp;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:170:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |             if(id == s[i].size() || s[i][id].ff-s[i][id].ss+1 >= l)
      |                ~~~^~~~~~~~~~~~~~

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