Submission #775694

#	Time	Username	Problem	Language	Result	Execution time	Memory
775694		GusterGoose27	Meetings (IOI18_meetings)	C++17	0 / 100	39 ms	43788 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 75e4+5;
const int MAXH = 1e9;
const int MAXB = 20;

typedef long long ll;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;

vector<pil> edges[MAXN]; // node, cost (right inclusive, left exclusive)
vector<ll> ans;
int height[MAXN];
int qleft[MAXN];
int qright[MAXN];
pil line[MAXN];
ll lpos[MAXN];
ll right_cost[MAXN];
int par[MAXN][MAXB]; // 60 mb
int mx[MAXN][MAXB]; // also need this thing

int n, q;

bool less(int i, int j) {
    return pii(height[i], i) < pii(height[j], j);
}

bool more(int i, int j) {
    return pii(height[i], i) > pii(height[j], j);
}

ll intersect(int i, int j) {
    assert(line[j].first > line[i].first);
    return (line[i].second-line[j].second+line[j].first-line[i].first-1)/(line[j].first-line[i].first);
}

bool below(int i, int j) {
    if (j == 0) return 0;
    assert(line[j].first > line[i].first);
    ll cmp_pos = intersect(i, j);
    return cmp_pos <= lpos[j];
}

void dfs(int cur, int p=-1) { // slope = rightval, intercept = sum of going right + internal
    for (pil e: edges[cur]) {
        int nxt = e.first;
        right_cost[nxt] = right_cost[cur]+(ll)(nxt-cur)*height[nxt];
        line[nxt] = pil(height[nxt], right_cost[cur]+e.second-(ll)height[nxt]*nxt);
        dfs(nxt, cur);
    }
    if (cur > 0) { // where does the line fit in
        for (int b = MAXB-1; b >= 0; b--) { // number of line parents to go through
            if (below(cur, par[p][b])) p = par[p][b];
        }
        if (below(cur, p)) p = par[p][0];
        assert(!below(cur, p));
        par[cur][0] = p;
        if (p == 0) lpos[cur] = 0;
        else lpos[cur] = intersect(cur, p);
        for (int b = 1; b < MAXB; b++) par[cur][b] = par[par[cur][b-1]][b-1];
    }
}

int get_mx(int l, int r) {
    int b = (31-__builtin_clz(r-l+1));
    return max(mx[l][b], mx[r-(1<<b)][b]);
}

ll query(int i, int x) {
    return (ll)line[i].first*x+line[i].second;
}

ll make_ans(int i, int j) {
    int div = get_mx(i, j);
    ll add = (div-i+1)*height[div]-right_cost[div];
    int cur = j;
    for (int b = MAXB-1; b >= 0; b--) {
        if (par[cur][b] > div && j < lpos[par[cur][b]]) cur = par[cur][b];
    }
    if (par[cur][0] > div && j < lpos[par[cur][0]]) cur = par[cur][0];
    assert(par[cur][0] <= div || j >= lpos[par[cur][0]]);
    ll res = add+query(cur, j);
    // cerr << res << "\n";
    return res;
}

void solve() {
    for (int i = 0; i < n; i++) edges[i].clear();
    // CLEAR ALL VARIABLES
    for (int b = 0; b < MAXB; b++) {
        for (int i = 0; i < n; i++) {
            if (b == 0) {
                mx[i][b] = i;
                continue;
            }
            if (i+(1<<b) > n) continue;
            else if (more(mx[i][b-1], mx[i+(1<<(b-1))][b-1])) mx[i][b] = mx[i][b-1];
            else mx[i][b] = mx[i+(1<<(b-1))][b-1];
        }
    }
    vector<int> stck;
    stck.push_back(0);
    for (int i = 1; i < n; i++) {
        ll running = 0;
        int prv = i;
        while (more(i, stck.back())) {
            if (prv == i) {
                prv = stck.back();
                running = height[i];
            }
            else {
                running = min(running+height[prv]*(prv-stck.back()),
                    edges[stck.back()].back().second+(i-prv-1)*height[prv]+height[i]);
                prv = stck.back();
            }
            stck.pop_back();
        }
        if (prv == i) running = height[i];
        else running = min(running+height[prv]*(prv-stck.back()),
                    edges[stck.back()].back().second+(i-prv-1)*height[prv]+height[i]);
        edges[stck.back()].push_back(pil(i, running));
        stck.push_back(i);
    }
    dfs(0);
    for (int i = 0; i < q; i++) {
        ans[i] = min(ans[i], make_ans(qleft[i], qright[i]));
    }
}

vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
    q = l.size();
    n = h.size();
    ans = vector<ll>(q);
    fill(ans.begin(), ans.end(), (ll)MAXN*MAXH);
    height[0] = MAXH+1;
    for (int i = 0; i < n; i++) height[i+1] = h[i];
    for (int i = 0; i < q; i++) {
        qleft[i] = l[i]+1;
        qright[i] = r[i]+1;
    }
    n++;
    solve();
    for (int i = 1; i < (n+1)/2; i++) {
        swap(height[i], height[n-i]);
    }
    for (int i = 0; i < q; i++) {
        int tmp = qleft[i];
        qleft[i] = n-qright[i];
        qright[i] = n-tmp;
    }
    solve();
    return ans;
}

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