Submission #830478

#	Time	Username	Problem	Language	Result	Execution time	Memory
830478		79brue	Meetings (IOI18_meetings)	C++17	0 / 100	573 ms	786432 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define printf(...) 
#define puts(...)

using namespace std;

typedef long long ll;

int n, q;
ll arr[7502];
int ql[7502], qr[7502];
ll ans[7502];

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<ll, 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[7502], lc[7502], rc[7002];
int intvL[7002], intvR[7502], root;
int thisL[7502];

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[7502];

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[i];
            continue;
        }
        int l = ql[i], r = qr[i], x = mult * tree.query(1, 1, n, l, r).second;
        if(x==n) 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 Container{
    struct Segment{
        int l, r; ll a, b;
        Segment(){}
        Segment(int l, int r, ll a, ll b): l(l), r(r), a(a), b(b){}
    };
    ll lazy;
    deque<Segment> vec;

    Container(){
        lazy = 0;
        vec.clear();
    }

    void clear(){
        lazy = 0;
        vec.clear();
    }

    bool empty(){
        return vec.empty();
    }

    void swap(Container &r){
        ::swap(lazy, r.lazy);
        ::swap(vec, r.vec);
    }

    void push_back(ll x, ll v){
        vec.push_back(Segment(x, x, 0, v-lazy));
    }

    ll back(){
        Segment p = vec.back();
        return p.a*p.r+p.b+lazy;
    }

    void operator+=(Container &nxt){
        if(vec.size() > nxt.vec.size()){
            for(Segment &p: nxt.vec){
                vec.push_back(p);
                vec.back().b += nxt.lazy - lazy;
            }
            nxt.clear();
        }
        else{
            for(int i=(int)vec.size()-1; i>=0; i--){
                nxt.vec.push_front(vec[i]);
                nxt.vec.front().b += lazy - nxt.lazy;
            }
            vec.clear();
            swap(nxt);
        }
    }

    void operator+=(ll &x){
        lazy+=x;
    }

    void render(ll a, ll b){
        if(vec[0].a * vec[0].l + vec[0].b + lazy <= a * vec[0].l + b) return; /// 바꿀 게 없음
        ll lmost = vec[0].l, rmost = -1;
        while(!vec.empty()){
            Segment p = vec.front();
            if(p.a*p.r+p.b+lazy >= a*p.r+b){
                rmost = p.r;
                vec.pop_front();
                continue;
            }

            ll x = p.l - 1;
            while(x<p.r && p.a*(x+1)+p.b+lazy > a*(x+1)+b) x++;
            rmost = x-1;
            vec.front().l = x;
            break;

            x = ceil((long double)(p.b+lazy-b) / (long double)(a - p.a));
            rmost = x-1;
            vec.front().l = x;
            break;
        }
        vec.push_front(Segment(lmost, rmost, a, b-lazy));
    }

    ll get(ll x){
        int L = 0, R = (int)vec.size();
        while(L<R){
            int M = (L+R)/2;
            if(vec[M].r < x) L = M+1;
            else R = M;
        }
        return vec[L].a * x + vec[L].b + lazy;
    }
} DP[750002];

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]), DP[x].swap(DP[lc[x]]);
        DP[x].push_back(x, DP[x].back()+arr[x]);
    }
    else DP[x].push_back(x, arr[x]);

    if(rc[x]){
        dnc(rc[x]);
        /// DP[rc[x]] 앞부분을 다듬는다
        ll v = DP[x].back(), vAll = arr[x] * (x-L+1);
        DP[rc[x]] += vAll;
        DP[rc[x]].render(arr[x], v - arr[x] * x);
        DP[x] += DP[rc[x]];
    }

    for(int idx: vec[x]){
        ans[idx] = min(ans[idx], DP[x].get(qr[idx]) + arr[intvL[x]-1] * (intvL[x] - ql[idx]));
        //printf("Checking %d: maybe %lld + %lld = %lld\n", idx, DP[x].get(qr[idx]), arr[intvL[x]-1]*(intvL[x]-ql[idx]),
        //    DP[x].get(qr[idx]) + arr[intvL[x]-1] * (intvL[x] - ql[idx]));
    }

    printf("Container[%d]\n", x);
    for(Container::Segment p: DP[x].vec) printf("(%lld, %lld) - %lldx + %lld, \t", p.l, p.r, p.a, p.b + DP[x].lazy);
    puts("");
}

void calculateAnswer(){
    for(int i=1; i<=n; i++) DP[i].clear();
    dnc(root);
}

Compilation message (stderr)

meetings.cpp: In function 'void dnc(int)':
meetings.cpp:233:28: warning: variable 'p' set but not used [-Wunused-but-set-variable]
  233 |     for(Container::Segment p: DP[x].vec) printf("(%lld, %lld) - %lldx + %lld, \t", p.l, p.r, p.a, p.b + DP[x].lazy);
      |                            ^
meetings.cpp:207:23: warning: unused variable 'R' [-Wunused-variable]
  207 |     int L = intvL[x], R = intvR[x];
      |                       ^

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