Submission #1244938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244938		jeroenodb	Meetings (IOI18_meetings)	C++20	41 / 100	487 ms	91144 KiB

meetings

#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) begin(x),end(x)
const int oo = 1e9;
const int N = 21;
struct node {
    int mx=0;
    int cl[N], cr[N];
    int lmx[N], rmx[N];
    node() {
        for(int i=0;i<N;++i) lmx[i]=oo,rmx[i]=oo;
        for(int i=0;i<N;++i) {
            cl[i]=cr[i]=0;
        }
    }
    node(int v) {
        *this=node();
        mx=v;
        lmx[v]=v;
        rmx[v]=v;
        for(int i=0;i<N;++i) {
            cl[i]=max(v,i);
            cr[i]=max(v,i);
        }
    }
    void merge(const node& o) {
        array<int,N> resl, resr;
        fill(all(resl),oo), fill(all(resr),oo);
        auto take = [&](int l, int val, int r) {
            if(val>=oo) return;

            if(l>r) {
                resl[r]=min(resl[r],val);
            } else resr[l]=min(resr[l],val);
        };
        for(int i=0;i<=max(mx,o.mx);++i) {
            take(mx, lmx[i] + o.cl[i], max(o.mx,i));
            take(i, rmx[i]  + o.cl[mx], max(o.mx,mx));
            take(max(mx,i), cr[i] + o.rmx[i], o.mx);
            take(max(mx,o.mx), cr[o.mx] + o.lmx[i], i);
        }
        for(int i=0;i<N;++i) {
            cl[i] += o.cl[max(i,mx)];
            cr[i] = cr[max(i,o.mx)] + o.cr[i];
        }
        copy(all(resl),lmx);
        copy(all(resr),rmx);
        mx=max(mx,o.mx);
        
    }
    friend node merge(node a, const node& b) {
        a.merge(b);
        return a;
    }
};
struct segtree {
    vector<node> s;
    int ptwo=1;
    segtree(int n) {
        while(ptwo<n) ptwo*=2;
        s.resize(ptwo*2,{});
    }
    void build() {
        for(int i=ptwo-1;i>=1;--i) {
            s[i] = merge(s[i*2],s[i*2+1]);
        }
    }
    node query(int l, int r) { // [l,r]
        l+=ptwo,r+=ptwo;
        node resl, resr;
        while(l<=r) {
            if(l%2==1) {
                resl.merge(s[l]);
                l++;
            }
            if(r%2==0) {
                resr = merge(s[r],resr);
                r--;
            }
            l/=2;
            r/=2;
        }
        return merge(resl,resr);
    }
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
                                    
    int Q = L.size();
    int mx = *max_element(all(H));
    assert(mx<=20);
    int n = H.size();
    segtree seg(n);
    for(int i=0;i<n;++i) {
        seg.s[seg.ptwo+i]=H[i];
    }
    seg.build();
    std::vector<long long> C;
    for(int i=0;i<Q;++i) {
        int l= L[i],r = R[i];
        auto res = seg.query(l,r);
        int ans = oo;
        for(int i=0;i<N;++i) {
            ans=min(ans,res.lmx[i]);
            ans=min(ans,res.rmx[i]);
            
        }
        C.push_back(ans);
    }
    return C;
}

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