Submission #425291

#	Time	Username	Problem	Language	Result	Execution time	Memory
425291		Peti	Meetings (IOI18_meetings)	C++14	0 / 100	113 ms	30008 KiB

meetings

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

using namespace std;

struct segment_tree{
    vector<int> st, v;
    int maxn;

    int get(int x, int y){
        if(x == maxn) return y;
        if(y == maxn) return x;
        return v[x] >= v[y] ? x : y;
    }

    void init(vector<int> ert, int n){
        maxn = n;
        while(maxn != (maxn&(-maxn))) maxn += (maxn&(-maxn));
        v = ert;
        st.resize(maxn<<1, maxn);
        iota(st.begin()+maxn, st.begin()+maxn+n, 0);
        for(int i = maxn-1; i > 0; i--)
            st[i] = get(st[2*i], st[2*i+1]);
    }

    int query(int s, int e, int x, int l, int r){
        if(e <= l || r <= s)
            return maxn;
        if(s <= l && r <= e)
            return st[x];
        int m = (l+r)/2;
        return get(query(s, e, 2*x, l, m), query(s, e, 2*x+1, m, r));
    }

    int query(int l, int r){
        return query(l, r, 1, 0, maxn);
    }
};

struct node{
    int l, r, lc, rc;
    long long ert;
    node *L = nullptr, *R = nullptr;

    node(){}
    node(node *L, node *R, int l, int r, int lc, int rc) : L(L), R(R), l(l), r(r), lc(lc), rc(rc) {};
};
typedef node* gnode;

struct st_adat{
    long long ossz, ert, hl, hr, len;
};
struct adat{
    int ind, l, r;
};

const long long INF = (long long)1e18;

segment_tree maxST;
vector<int> h;

gnode build(int l, int r, int lc, int rc){
    if(l+1 == r){
        gnode temp = new node(nullptr, nullptr, l, r, lc, rc);
        temp->ert = h[l];
        return temp;
    }
    int m = maxST.query(l, r);
    int c = h[m];
    if(m == l) m++;
    gnode p = new node(build(l, m, lc, c), build(m, r, c, rc), l, r, lc, rc);
    p->ert = min(p->L->ert + (long long)(r-m)*c, p->R->ert + (long long)(m-l)*c);
    return p;
}

const int stn = 1<<20;
st_adat st[stn<<1];

void kiir(gnode p){
    cout<<"node: ("<<(p->l)<<", "<<(p->r)<<")  ert: "<<p->ert<<"  cl: "<<p->lc<<"  cr: "<<p->rc<<"\n";
}

void kiir(st_adat d){
    cout<<"st_adat: "<<d.ossz<<" "<<d.ert<<" "<<d.hl<<" "<<d.hr<<" "<<d.len<<"\n";
}

st_adat get(st_adat ld, st_adat rd){
    if(ld.ossz == INF) return rd;
    if(rd.ossz == INF) return ld;
    return {ld.ossz + rd.ossz, min(ld.ert + rd.len*ld.hr, rd.ert + ld.ossz), ld.hl, rd.hr, ld.len+rd.len};
}

void add(int x, st_adat d){
    st[x+stn] = d;
    //cout<<"add: ";
    //kiir(d);
    for(int i = (x+stn)>>1; i > 0; i >>= 1)
        st[i] = get(st[2*i], st[2*i+1]);
}

st_adat query(int s, int e, int x, int l, int r){
    if(r <= s || e <= l)
        return {INF};
    if(s <= l && r <= e){
        //cout<<"\n";
        //cout<<"st query: "<<l<<" "<<r<<" "<<x<<"\n";
        //kiir(st[x]);
        //cout<<"\n";
        return st[x];
    }
    int m = (l+r)/2;
    return get(query(s, e, 2*x, l, m), query(s, e, 2*x+1, m, r));
}

vector<vector<adat>> vegek((int)1e6);
vector<long long> meg;

int starts[(int)1e6];

void add_node(gnode p, int ind){
    starts[ind] = p->l;
    long long ossz = (long long)(p->r-p->l)*p->rc;
    if(h[p->l] > p->rc) ossz += (long long)(h[p->l] - p->rc);
    //cout<<"add from node: ";
    //kiir(p);
    add(ind, {ossz, p->ert, p->lc, p->rc, p->r-p->l});
}

void bejar(gnode p, int len){
    //kiir(p);
    if(p->l+1 == p->r){
        /*cout<<"Ind: "<<p->l<<" "<<vegek[p->l].size()<<" "<<len<<"\n";
        for(int i = 0; i < len; i++)
            cout<<starts[i]<<" ";
        cout<<" sor\n";*/
        for(adat d : vegek[p->l]){
            int m = lower_bound(starts, starts+len, d.l)-starts;
            if(m == len) continue;
            //cout<<m<<" "<<starts[m]<<" "<<len<<" check\n";
            st_adat x = query(m, len, 1, 0, stn);
            //kiir(x);
            meg[d.ind] = min(meg[d.ind], x.ert + x.hl*(starts[m]-d.l));
        }
        return;
    }
    bejar(p->L, len);
    add_node(p->L, len);
    bejar(p->R, len+1);
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
    H.push_back((int)1e9+1);
    H.insert(H.begin(), (int)1e9+1);
    int n = (int)H.size();
    int q = (int)L.size();
    h = H;
    meg.resize(q, INF);

    maxST.init(H, n);
    for(int i = 0; i < q; i++)
        vegek[R[i]+2].push_back({i, L[i]+1, R[i]+1});
    bejar(build(0, n, 0, 0), 0);

    for(int i = 0; i < q; i++)
        vegek[R[i]+2].clear();

    reverse(h.begin(), h.end());
    maxST.init(h, n);
    for(int i = 0; i < q; i++)
        vegek[n-L[i]-1].push_back({i, n-R[i]-2, n-L[i]-2});
    bejar(build(0, n, 0, 0), 0);

    return meg;
}

Compilation message (stderr)

meetings.cpp: In constructor 'node::node(node*, node*, int, int, int, int)':
meetings.cpp:43:25: warning: 'node::R' will be initialized after [-Wreorder]
   43 |     node *L = nullptr, *R = nullptr;
      |                         ^
meetings.cpp:41:9: warning:   'int node::l' [-Wreorder]
   41 |     int l, r, lc, rc;
      |         ^
meetings.cpp:46:5: warning:   when initialized here [-Wreorder]
   46 |     node(node *L, node *R, int l, int r, int lc, int rc) : L(L), R(R), l(l), r(r), lc(lc), rc(rc) {};
      |     ^~~~

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