Submission #571173

#	Time	Username	Problem	Language	Result	Execution time	Memory
571173		elazarkoren	Meetings (IOI18_meetings)	C++17	0 / 100	294 ms	2764 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const ll infinity = 1e18;

struct Seg {
    int n;
    vi seg, add;
    Seg () {}
    Seg (int m) {
        for (n = 1; n < m; n <<= 1);
        seg.resize(2 * n), add.resize(2 * n);
    }
    inline void pull(int i) {
        seg[i] = min(Val(i << 1), Val(i << 1 | 1));
    }
    inline void push(int i) {
        add[i << 1] += add[i];
        add[i << 1 | 1] += add[i];
        seg[i] += add[i];
        add[i] = 0;
    }
    inline ll Val(int i) {
        return seg[i] + add[i];
    }
    void update(int a, int b, ll x, int ind, int l, int r) {
        if (a <= l && r <= b) {
            add[ind] += x;
            return;
        }
        if (r <= a || b <= l) return;
        push(ind);
        update(a, b, x, ind << 1, l, (l + r) >> 1);
        update(a, b, x, ind << 1 | 1,(l + r) >> 1, r);
        pull(ind);
    }
    inline void update(int a, int b, ll x) {
        update(a, b, x, 1, 0, n);
    }
    ll query(int a, int b, int ind, int l, int r) {
        if (a <= l && r <= b) return Val(ind);
        if (r <= a || b <= l) return infinity;
        push(ind);
        return min(query(a, b, ind << 1, l, (l + r) >> 1),
                   query(a, b, ind << 1 | 1,(l + r) >> 1, r));
    }
    inline ll query(int a, int b) {
        return query(a, b, 1, 0, n);
    }
};

const int block = 250;
const int MAX_N = 1e5 + 5;

int lefts[MAX_N], rights[MAX_N];
ll h[MAX_N];
int n;

Seg seg;

void Add(int i, int x) {
    int v = i;
    while (v != -1) {
        int nex = lefts[v];
        seg.update(nex + 1, v + 1, x * h[v]);
        v = nex;
    }
    v = i;
    while (v != n) {
        int nex = rights[v];
        seg.update(v, nex, x * h[v]);
        v = nex;
    }
    seg.update(i, i + 1, -x * h[i]);
}

int cnt[MAX_N][25];
int fir[25], last[25];

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int q = L.size();
    n = H.size();
    for (int i = 0; i < n; i++) h[i] = H[i];
    vector<long long> ans(q);
    stack<int> stk;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && h[stk.top()] <= h[i]) stk.pop();
        lefts[i] = stk.empty() ? -1 : stk.top();
        stk.push(i);
    }
    while (!stk.empty()) stk.pop();
    for (int i = n - 1; i >= 0; i--) {
        while (!stk.empty() && h[stk.top()] <= h[i]) stk.pop();
        rights[i] = stk.empty() ? n : stk.top();
        stk.push(i);
    }
    cnt[0][h[0]] = 1;
    for (int i = 1; i < n; i++) {
        for (int x = 1; x <= 20; x++) {
            cnt[i][x] = cnt[i - 1][x] + (h[i] == x);
        }
        if (cnt[i][h[i]] == 1) fir[h[i]] = i;
        chkmax(last[h[i]], i);
    }
    seg = Seg(n);
    for (int i = 0; i < n; i++) {
        Add(i, 1);
    }
    for (int j = 0; j < q; j++) {
        int l = L[j], r = R[j];
        if (l) {
            for (int x = 1; x <= 20; x++) {
                if (cnt[l - 1][x]) {
                    Add(fir[x], -cnt[l - 1][x]);
                }
            }
        }
        if (r < n - 1) {
            for (int x = 1; x <= 20; x++) {
                if (cnt[n - 1][x] - cnt[r][x]) {
                    Add(last[x], -(cnt[n - 1][x] - cnt[r][x]));
                }
            }
        }
        ans[j] = seg.query(l, r + 1);
        if (l) {
            for (int x = 1; x <= 20; x++) {
                if (cnt[l - 1][x]) {
                    Add(fir[x], cnt[l - 1][x]);
                }
            }
        }
        if (r < n - 1) {
            for (int x = 1; x <= 20; x++) {
                if (cnt[n - 1][x] - cnt[r][x]) {
                    Add(last[x], cnt[n - 1][x] - cnt[r][x]);
                }
            }
        }
    }
//    int a = 0, b = -1;
//    vi ind(q);
//    iota(all(ind), 0);
//    sort(all(ind), [&] (int i, int j) {
//        return L[i] / block == L[j] / block ? R[i] < R[j] : L[i] < L[j];
//    });
//    for (int j : ind) {
//        int l = L[j], r = R[j];
//        while (a < l) {
//            Add(a++, -1);
//        }
//        while (a > l) {
//            Add(--a, 1);
//        }
//        while (b < r) {
//            Add(++b, 1);
//        }
//        while (b > r) {
//            Add(b--, -1);
//        }
//        ans[j] = seg.query(l, r + 1);
//    }
    return ans;
}
//10 3
//1 2 2 1 1 1 2 1 1 2
//2 5
//3 7
//4 9

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