Submission #831635

#	Time	Username	Problem	Language	Result	Execution time	Memory
831635		79brue	Meetings (IOI18_meetings)	C++17	100 / 100	2263 ms	276108 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int MX = 750002;
 
inline ll divFloor(ll a, ll b){
    if(a>=0) return a/b;
    else return -((-a+b-1)/b);
}
 
inline ll divCeil(ll a, ll b){
    if(b<0) a=-a, b=-b;
    return divFloor(a+b-1, b);
}
 
int n, q;
ll arr[MX];
int ql[MX], qr[MX];
ll ans[MX];
 
void solve();
 
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
    n = (int)H.size();
    for(int i=1; i<=n; i++) arr[i] = H[i-1];
    q = (int)L.size();
    for(int i=1; i<=q; i++) ql[i] = L[i-1]+1, qr[i] = R[i-1]+1, ans[i] = LLONG_MAX;
 
    solve();
 
    vector<ll> ret;
    for(int i=1; i<=q; i++) ret.push_back(ans[i]);
    return ret;
}
 
void makeCartesianTree();
void reformQuery();
void calculateAnswer();
 
int mult = 1;
void solve(){
    makeCartesianTree();
    reformQuery();
    calculateAnswer();
 
    reverse(arr+1, arr+n+1);
    for(int i=1; i<=q; i++) ql[i] = n+1-ql[i], qr[i] = n+1-qr[i], swap(ql[i], qr[i]);
    mult = -1;
 
    makeCartesianTree();
    reformQuery();
    calculateAnswer();
}
 
struct segTree{
    pair<int, int> tree[1<<21];
 
    void init(int i, int l, int r, ll *A){
        if(l==r){
            tree[i] = make_pair(A[l], l * mult);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }
 
    pair<int, int> query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return make_pair(0, 0);
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} tree;
 
int par[MX], lc[MX], rc[MX];
int intvL[MX], intvR[MX], root;
int thisL[MX];
 
int dnc(int l, int r, int p=0){
    if(l>r) return 0;
    int x = mult * tree.query(1, 1, n, l, r).second;
    par[x] = p;
    intvL[x] = l, intvR[x] = r;
    lc[x] = dnc(l, x-1);
    rc[x] = dnc(x+1, r);
    thisL[intvL[x]] = x;
    // printf("thisL[%d] = %d\n", intvL[x], x);
    return x;
}
 
void makeCartesianTree(){
    for(int i=1; i<=n; i++){
        par[i] = lc[i] = rc[i] = thisL[i] = 0;
    }
    tree.init(1, 1, n, arr);
    root = dnc(1, n);
}
 
vector<int> vec[MX];
 
void reformQuery(){
    for(int i=1; i<=n; i++) vec[i].clear();
    for(int i=1; i<=q; i++){
        if(ql[i] == qr[i]){
            ans[i] = arr[ql[i]];
            continue;
        }
        int l = ql[i], r = qr[i], x = mult * tree.query(1, 1, n, l, r).second;
        if(x==qr[i]) ans[i] = min(ans[i], arr[x] * (r-l+1));
        else vec[thisL[x+1]].push_back(i);
 
        //printf("Pushed %d to %d (x %d)\n", i, thisL[x+1], x);
    }
}

struct myList{
    int frontIdx;
    vector<int> vecFront, vecBack; /// index: ~ -1, 0 ~ 

    myList(){
        vecFront.clear();
        vecBack.clear();
        frontIdx = 0;
    }

    bool empty(){
        return size() == 0;
    }

    void clear(){
        vecFront.clear();
        vecBack.clear();
        frontIdx = 0;
    }

    int &back(){
        return frontIdx<0 ? vecFront[-frontIdx] : vecBack.empty() ? vecFront[0] : vecBack.back();
    }

    void push_back(int x){
        if(frontIdx < 0) vecFront[-(++frontIdx)] = x;
        else vecBack.push_back(x);
    }

    void pop_back(){
        if(vecBack.empty()) frontIdx--;
        else vecBack.pop_back();
    }

    int &front(){
        return frontIdx>0 ? vecBack[frontIdx] : vecFront.empty() ? vecBack[0] : vecFront.back();
    }

    void push_front(int x){
        if(frontIdx > 0) vecBack[--frontIdx] = x;
        else vecFront.push_back(x);
    }

    void pop_front(){
        if(vecFront.empty()) frontIdx++;
        else vecFront.pop_back();
    }

    int biggestLess(int x){
        //printf("frontIdx: %d, x: %d\n", frontIdx, x);
        //printf("vecFront: "); for(int x: vecFront) printf("%d ", x); puts(""); 
        //printf("vecBack: "); for(int x: vecBack) printf("%d ", x); puts("");
        if(frontIdx > 0){
            return *prev(upper_bound(vecBack.begin() + frontIdx, vecBack.end(), x));
        }
        else if(frontIdx < 0){
            return *lower_bound(vecFront.begin() - frontIdx, vecFront.end(), x, greater<int> ());
        }
        else{
            if(!vecBack.empty() && vecBack[0] <= x)
                return *prev(upper_bound(vecBack.begin(), vecBack.end(), x));
            return *lower_bound(vecFront.begin(), vecFront.end(), x, greater<int> ());
        }
    }

    int size(){
        return (int)vecFront.size() + (int)vecBack.size() - abs(frontIdx);
    }

    void swap(myList &nxt){
        ::swap(vecFront, nxt.vecFront);
        ::swap(vecBack, nxt.vecBack);
        ::swap(frontIdx, nxt.frontIdx);
    }
};

ll lazy[MX]; int rEnd[MX];
ll setA[MX], setB[MX];
myList dq[MX];
 
ll backVal(int x){
    int t = dq[x].back();
    // printf("backVal[%d] = %lld (t=%d)\n", x, setA[t] * rEnd[t] + setB[t] + lazy[x], t);
    return setA[t] * rEnd[t] + setB[t] + lazy[x];
}
 
ll calc(int x, ll v){
    int p = dq[x].biggestLess(v);
    return setA[p] * v + setB[p] + lazy[x];
}
 
void render(int x, ll a, ll b){
    if(dq[x].empty() || setA[dq[x].front()] * dq[x].front() + setB[dq[x].front()] + lazy[x] <= a*dq[x].front()+b)
        return;
    ll L = dq[x].front(), R = L-1;
    while(!dq[x].empty()){
        int f = dq[x].front();
        if(setA[f] * f + setB[f] + lazy[x] <= a * f + b) break;
        if(setA[f] * rEnd[f] + setB[f] + lazy[x] >= a * rEnd[f] + b){
            R = rEnd[f];
            dq[x].pop_front();
            continue;
        }
 
        //while(setA[f] * (R+1) + setB[f] + lazy[x] > a * (R+1) + b) R++;
        //dq[x].front() = R+1;
        //setA[R+1] = setA[f], setB[R+1] = setB[f], rEnd[R+1] = rEnd[f];
        //if(R+1 != f) setA[f] = setB[f] = rEnd[f] = 0;
        //break;
 
        ll ad = a - setA[f], bd = setB[f] + lazy[x] - b;
        assert(ad > 0 && bd >= 0);
        ll newL = divCeil(bd, ad);
        R = newL - 1;
        dq[x].front() = newL;
        setA[newL] = setA[f], setB[newL] = setB[f], rEnd[newL] = rEnd[f];
        if(newL != f) setA[f] = setB[f] = rEnd[f] = 0;
        break;
    }
    //printf("After render, [%d - %d] is formed\n", L, R);
    if(L<=R){
        dq[x].push_front(L);
        rEnd[L] = R;
        setA[L] = a, setB[L] = b - lazy[x];
 
        //printf("dq[%d]: ", x); for(int p: dq[x]) printf("%d ", p); puts("");
    }
}
 
void merge(ll a, ll b){
    if((int)dq[a].size() > dq[b].size()){
        while(!dq[b].empty()){
            int x = dq[b].front(); dq[b].pop_front();
            dq[a].push_back(x), setB[x] += lazy[b] - lazy[a];
        }
    }
    else{
        while(!dq[a].empty()){
            dq[b].push_front(dq[a].back()); dq[a].pop_back();
            setB[dq[b].front()] += lazy[a] - lazy[b];
        }
        dq[a].swap(dq[b]);
        lazy[a] = lazy[b];
    }
    dq[b].clear();
}
 
void dnc(int x){
    int L = intvL[x], R = intvR[x];
    // printf("dnc %d %d %d\n", x, L, R);
 
    /// [L, x]
    if(lc[x]){
        dnc(lc[x]);
        lazy[x] = lazy[lc[x]], dq[x].swap(dq[lc[x]]);
        setA[x] = 0, setB[x] = backVal(x) + arr[x] - lazy[x];
        dq[x].push_back(x);
    }
    else{
        dq[x].push_back(x);
        rEnd[x] = x;
        setA[x] = 0, setB[x] = arr[x] - lazy[x];
    }
 
    if(rc[x]){
        dnc(rc[x]);
        /// DP[rc[x]] 앞부분을 다듬는다
        ll v = backVal(x), vAll = arr[x] * (x-L+1);
        // printf("Added %lld to %d\n", vAll, rc[x]);
        lazy[rc[x]] += vAll;
        render(rc[x], arr[x], v-arr[x]*x);
        merge(x, rc[x]);
    }
 
    for(int idx: vec[x]){
        ans[idx] = min(ans[idx], calc(x, qr[idx]) + arr[intvL[x]-1] * (intvL[x] - ql[idx]));
        //printf("Checking %d: maybe %lld + %lld = %lld\n", idx, calc(x, qr[idx]), arr[intvL[x]-1]*(intvL[x]-ql[idx]),
        //    calc(x, qr[idx]) + arr[intvL[x]-1] * (intvL[x] - ql[idx]));
    }
 
    //printf("Deque of %d\n", x);
    //for(int p: dq[x]) printf("[%d-%d] %lldx + %lld, \t", p, rEnd[p], setA[p], setB[p]+lazy[x]); puts("");
}
 
void calculateAnswer(){
    for(int i=1; i<=n; i++){
        lazy[i] = 0, rEnd[i] = i, setA[i] = setB[i] = 0;
        dq[i].clear();
    }
    dnc(root);
}

Compilation message (stderr)

meetings.cpp: In function 'void dnc(int)':
meetings.cpp:269:23: warning: unused variable 'R' [-Wunused-variable]
  269 |     int L = intvL[x], R = intvR[x];
      |                       ^

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