Submission #139323

#	Time	Username	Problem	Language	Result	Execution time	Memory
139323		Meloric	Meetings (IOI18_meetings)	C++14	36 / 100	997 ms	9772 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define X first
#define Y second

using namespace std;

ll ez(int l, int r, vector<int>& H){
    vector<ll> le, ri, st, am;
    le.assign(H.size(), 0);
    ri.assign(H.size(), 0);
    ll cur = 0;
    for(int i = l; i<=r; i++){
        ll tmp = 1;
        while(st.size()>0 && st.back() <= H[i]){
            tmp+=am.back();
            cur-=am.back()*st.back();
            st.pop_back();
            am.pop_back();
        }
        cur+=tmp*H[i];
        le[i] = cur;
        st.pb((ll)H[i]);
        am.pb(tmp);
    }
    cur = 0;
    st.clear(); am.clear();
    for(int i = r; i>=l; i--){
        ll tmp = 1;
        while(st.size()>0 && st.back() <= H[i]){
            tmp+=am.back();
            cur-=am.back()*st.back();
            st.pop_back();
            am.pop_back();
        }
        cur+=tmp*H[i];
        ri[i] = cur;
        st.pb((ll)H[i]);
        am.pb(tmp);
    }
    ll ret = 1e15;
    for(int i = l; i<=r; i++){
        ret = min(ret, le[i]+ri[i]-H[i]);
    }
    return ret;
}
struct node{
    int prf, suf, sum, flag;
};
vector<node> seg;
node conq(node& a, node& b){
    node c;
    c.flag = a.flag & b.flag;
    if(a.flag){
        c.prf = a.sum + b.prf;
    }else{
        c.prf = a.prf;
    }
    if(b.flag){
        c.suf = a.suf + b.sum;
    }else{
        c.suf = b.suf;
    }
    c.sum = max(a.sum, b.sum);
    c.sum = max(c.sum, a.suf + b. prf);
    return c;
}
void build(int v, int tl, int tr, vector<int>& H){
    if(tl ==  tr){
        if(H[tl] == 1){
            seg[v] = {1, 1, 1, 1};
        }
        return;
    }
    int tm = (tl+tr)/2;
    build(v*2, tl, tm, H);
    build(v*2+1, tm+1, tr, H);
    seg[v] = conq(seg[2*v], seg[2*v+1]);
}
node qer(int v, int tl, int tr, int l, int r){
    if(tl > r || tr < l)return {-1, -1, -1, -1};
    if(tl >= l && tr <= r)return seg[v];
    int tm = (tl+tr)/2;
    node le = qer(v*2, tl, tm, l, r);
    node ri = qer(v*2+1, tm+1, tr, l, r);
    if(le.flag == -1)return ri;
    if(ri.flag == -1)return le;
    return conq(le, ri);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,
                                     vector<int> R) {
  int Q = L.size();
  int N = H.size();
  vector<ll> C(Q);
  if(N <= 5005 && Q <= 5005){
    for (int j = 0; j < Q; ++j) {
        C[j] = ez(L[j], R[j], H);
    }
    return C;
  }
  seg.assign(4*N, {0, 0, 0, 0});
  build(1, 0, N-1, H);
  for (int j = 0; j < Q; ++j) {
    int sum =  qer(1, 0, N-1, L[j], R[j]).sum;
    sum+=(R[j]-L[j]+1-sum)*2;
    C[j] = sum;
  }
  return C;
}

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