Submission #293185

#	Time	Username	Problem	Language	Result	Execution time	Memory
293185		Hideo	Meetings (IOI18_meetings)	C++17	41 / 100	870 ms	45384 KiB

meetings

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

using namespace std;

#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define pi pair < int, int >

const int N = 1e5 + 7;
const int INF = 1e9 + 7;

int t[4 * N], lz[4 * N];
int prv[N][22], nxt[N][22];
int pr[N][22], prc[N][22], total[N];
int a[N], ans[N];
int n, q;

pair < pi, int > qr[N];
vector < ll > ret;

void push (int v, int l, int r){
    if (l != r){
        lz[v + v] += lz[v];
        lz[v + v + 1] += lz[v];
    }
    t[v] += lz[v];
    lz[v] = 0;
}

void upd (int v, int l, int r, int ql, int qr, int val){
    push(v, l, r);
    if (r < ql || qr < l)
        return;
    if (ql <= l && r <= qr){
        lz[v] += val;
        push(v, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    upd(v + v, l, mid, ql, qr, val);
    upd(v + v + 1, mid + 1, r, ql, qr, val);
    t[v] = min(t[v + v], t[v + v + 1]);
}

int get (int v, int l, int r, int ql, int qr){
    push(v, l, r);
    if (r < ql || qr < l)
        return INF;
    if (ql <= l && r <= qr)
        return t[v];
    int mid = (l + r) >> 1;
    return min(get(v + v, l, mid, ql, qr), get(v + v + 1, mid + 1, r, ql, qr));
}

void build (int v, int l, int r){
    if (l == r){
        int last = n + 1;
        for (int j = 20; j >= 1; j--){
            prc[l][j] = last - l;
            if (last > nxt[l][j]){
                pr[l][j] = (last - nxt[l][j]) * j;
                t[v] += pr[l][j];
                last = nxt[l][j];
            }
        }
        total[l] = t[v];
        last = 0;
        for (int j = 20; j >= 1; j--){
            if (last < prv[l][j]){
                t[v] += (prv[l][j] - last) * j;
                last = prv[l][j];
            }
        }
        t[v] -= a[l];
    }
    else {
        int mid = (l + r) >> 1;
        build(v + v, l, mid);
        build(v + v + 1, mid + 1, r);
        t[v] = min(t[v + v], t[v + v + 1]);
    }
}

void change (int l){
    int last = n + 1;
    for (int j = 20; j >= 1; j--){
        if (last > nxt[l][j]){
            upd(1, 1, n, nxt[l][j], last - 1, -j);
            last = nxt[l][j];
        }
    }
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    n = H.size();
    q = L.size();
    for (int i = 0; i < n; i++)
        a[i + 1] = H[i];
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= 20; j++)
            prv[i][j] = prv[i - 1][j];
        prv[i][a[i]] = i;
    }
    for (int j = 1; j <= 20; j++)
        nxt[n + 1][j] = n + 1;
    for (int i = n; i >= 1; i--){
        for (int j = 1; j <= 20; j++)
            nxt[i][j] = nxt[i + 1][j];
        nxt[i][a[i]] = i;
    }
    build(1, 1, n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 20; j++)
            pr[i][j] += pr[i][j - 1];
    for (int i = 0; i < q; i++)
        qr[i + 1] = {{L[i] + 1, R[i] + 1}, i + 1};
    sort(qr + 1, qr + 1 + q);
    int l = 1;
    for (int i = 1; i <= q; i++){
        while (qr[i].fr.fr > l){
            change(l);
            l++;
        }
        int r = qr[i].fr.sc, last = l - 1, res = INF;
        for (int j = 20; j >= 1; j--){
            if (last < prv[r][j] && prv[r][j] >= l){
                res = min(res, get(1, 1, n, last + 1, prv[r][j]) - (total[r + 1] - pr[r + 1][j] + prc[r + 1][j] * j));
                last = prv[r][j];
            }
        }
        ans[qr[i].sc] = res;
    }
    for (int i = 1; i <= q; i++)
        ret.pb(1ll * ans[i]);
    return ret;
}

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