oj.uz

Submission #116180

# Submission time Handle Problem Language Result Execution time Memory
116180 2019-06-11T05:48:28 Z tri Meetings (IOI18_meetings) C++14
100 / 100
 4661 ms 398640 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = false;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.y, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"); }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

const int MAXN = 1e6 + 5;
const int LOGN = 21;
const ll INF = 1e16;

struct Line {
    ll m;
    ll b;

    ll y(int x) {
        return m * x + b;
    }

    Line(ll mI = 0, ll bI = INF) {
        m = mI;
        b = bI;
    }
};

Line tr[4 * MAXN];
ll lz[4 * MAXN];

void uL(int i, int l, int r, int s, int e, Line line) {
    if (e < l || r < s) {
        return;
    }
    line.b -= lz[i];
    if (s <= l && r <= e) {
        if (l == r) {
            if (line.y(l) < tr[i].y(l)) {
                tr[i] = line;
            }
        } else {
            int mid = (l + r) / 2;
            bool bF = line.y(l) < tr[i].y(l);
            bool bM = line.y(mid) < tr[i].y(mid);

            if (bF) {
                if (bM) {
                    swap(tr[i], line);
                    uL(i * 2 + 1, mid + 1, r, s, e, line);
                } else {
                    uL(i * 2, l, mid, s, e, line);
                }
            } else {
                if (bM) {
                    swap(tr[i], line);
                    uL(i * 2, l, mid, s, e, line);
                } else {
                    uL(i * 2 + 1, mid + 1, r, s, e, line);
                }
            }
        }
        return;
    }
    int mid = (l + r) / 2;
    uL(i * 2, l, mid, s, e, line);
    uL(i * 2 + 1, mid + 1, r, s, e, line);
}

void uC(int i, int l, int r, int s, int e, ll d) {
    if (e < l || r < s) {
        return;
    }

    if (s <= l && r <= e) {
        lz[i] += d;
        return;
    }

    int mid = (l + r) / 2;
    uC(i * 2, l, mid, s, e, d);
    uC(i * 2 + 1, mid + 1, r, s, e, d);
}

ll q(int i, int l, int r, int x) {
    if (l == r) {
        return lz[i] + tr[i].y(x);
    }
    int mid = (l + r) / 2;
    if (x <= mid) {
        return lz[i] + min(tr[i].y(x), q(i * 2, l, mid, x));
    } else {
        return lz[i] + min(tr[i].y(x), q(i * 2 + 1, mid + 1, r, x));
    }
}

int log2d(int x) {
    return 31 - __builtin_clz(x);
}

pi tb[MAXN][LOGN];

void init() {
    for (int k = 1; k < LOGN; k++) {
        for (int i = 0; i < MAXN; i++) {
            int nI = i + (1 << (k - 1));
            if (nI < MAXN) {
                tb[i][k] = max(tb[i][k - 1], tb[nI][k - 1]);
            } else {
                tb[i][k] = tb[i][k - 1];
            }
        }
    }
}

pi qMax(int l, int r) {
    int k = log2d(r - l + 1);
    return max(tb[l][k], tb[r - (1 << k) + 1][k]);
}

struct Query {
    int l;
    int r;
    int i;
};

vector<Query> queries[MAXN];
vl ans;

int N, Q;

void process(int l, int r) {
    // ps("process", l, r);
    pi mP = qMax(l, r);
    ll mH = mP.f;
    int mI = abs(mP.s);

    if (l < mI) {
        process(l, mI - 1);
    }
    if (mI < r) {
        process(mI + 1, r);
    }

    for (Query cQ : queries[mI]) {
        if (cQ.r > mI) {
            ans[cQ.i] = min(ans[cQ.i], q(1, 1, MAXN, cQ.r) + (mI - cQ.l + 1ll) * mH);
        }
    }

    uC(1, 1, MAXN, mI, r, (mI - l + 1ll) * mH);
    ll lCost = l < mI ? q(1, 1, MAXN, mI - 1) : 0;
    uL(1, 1, MAXN, mI, r, Line(mH, lCost - (mI - 1ll) * mH));
}

void calculate(vi &H, vi &L, vi &R, int flip = 1) {
    for (int i = 0; i < 4 * MAXN; i++) {
        tr[i] = Line();
        lz[i] = 0;
    }

    for (int i = 0; i < MAXN; i++) {
        queries[i].clear();
    }

    for (int i = 0; i < N; i++) {
        tb[i][0] = {H[i], i * flip};
    }
    init();

    for (int i = 0; i < Q; i++) {
        queries[flip * qMax(L[i], R[i]).s].pb({L[i], R[i], i});
    }
    process(0, N - 1);
}

vl minimum_costs(vi H, vi L, vi R) {
    ps("read");
    N = H.size();
    Q = L.size();
    ans.resize(Q, INF);

    calculate(H, L, R);

    // reverse
    for (int i = 0; i < N / 2; i++) {
        swap(H[i], H[N - 1 - i]);
    }
    for (int i = 0; i < Q; i++) {
        L[i] = N - 1 - L[i];
        R[i] = N - 1 - R[i];
        swap(L[i], R[i]);
    }
    //

    calculate(H, L, R, -1);

    for (int i = 0; i < Q; i++) {
        ans[i] = min(ans[i], (R[i] - L[i] + 1ll) * qMax(L[i], R[i]).f);
    }

    return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1107 ms 282160 KB Output is correct
2 Correct 1090 ms 282140 KB Output is correct
3 Correct 1088 ms 282188 KB Output is correct
4 Correct 1106 ms 282192 KB Output is correct
5 Correct 1106 ms 282188 KB Output is correct
6 Correct 1101 ms 282224 KB Output is correct
7 Correct 1131 ms 282056 KB Output is correct
8 Correct 1097 ms 282308 KB Output is correct
9 Correct 1097 ms 282236 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1107 ms 282160 KB Output is correct
2 Correct 1090 ms 282140 KB Output is correct
3 Correct 1088 ms 282188 KB Output is correct
4 Correct 1106 ms 282192 KB Output is correct
5 Correct 1106 ms 282188 KB Output is correct
6 Correct 1101 ms 282224 KB Output is correct
7 Correct 1131 ms 282056 KB Output is correct
8 Correct 1097 ms 282308 KB Output is correct
9 Correct 1097 ms 282236 KB Output is correct
10 Correct 1106 ms 282540 KB Output is correct
11 Correct 1107 ms 282612 KB Output is correct
12 Correct 1117 ms 282596 KB Output is correct
13 Correct 1107 ms 282580 KB Output is correct
14 Correct 1105 ms 282776 KB Output is correct
15 Correct 1105 ms 282596 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1103 ms 282112 KB Output is correct
2 Correct 1191 ms 285696 KB Output is correct
3 Correct 1420 ms 293508 KB Output is correct
4 Correct 1366 ms 289364 KB Output is correct
5 Correct 1394 ms 293108 KB Output is correct
6 Correct 1427 ms 294144 KB Output is correct
7 Correct 1439 ms 295416 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1103 ms 282112 KB Output is correct
2 Correct 1191 ms 285696 KB Output is correct
3 Correct 1420 ms 293508 KB Output is correct
4 Correct 1366 ms 289364 KB Output is correct
5 Correct 1394 ms 293108 KB Output is correct
6 Correct 1427 ms 294144 KB Output is correct
7 Correct 1439 ms 295416 KB Output is correct
8 Correct 1359 ms 289960 KB Output is correct
9 Correct 1289 ms 289620 KB Output is correct
10 Correct 1378 ms 290032 KB Output is correct
11 Correct 1342 ms 289332 KB Output is correct
12 Correct 1302 ms 288972 KB Output is correct
13 Correct 1363 ms 289796 KB Output is correct
14 Correct 1419 ms 294008 KB Output is correct
15 Correct 1338 ms 289208 KB Output is correct
16 Correct 1462 ms 293692 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1107 ms 282160 KB Output is correct
2 Correct 1090 ms 282140 KB Output is correct
3 Correct 1088 ms 282188 KB Output is correct
4 Correct 1106 ms 282192 KB Output is correct
5 Correct 1106 ms 282188 KB Output is correct
6 Correct 1101 ms 282224 KB Output is correct
7 Correct 1131 ms 282056 KB Output is correct
8 Correct 1097 ms 282308 KB Output is correct
9 Correct 1097 ms 282236 KB Output is correct
10 Correct 1106 ms 282540 KB Output is correct
11 Correct 1107 ms 282612 KB Output is correct
12 Correct 1117 ms 282596 KB Output is correct
13 Correct 1107 ms 282580 KB Output is correct
14 Correct 1105 ms 282776 KB Output is correct
15 Correct 1105 ms 282596 KB Output is correct
16 Correct 1103 ms 282112 KB Output is correct
17 Correct 1191 ms 285696 KB Output is correct
18 Correct 1420 ms 293508 KB Output is correct
19 Correct 1366 ms 289364 KB Output is correct
20 Correct 1394 ms 293108 KB Output is correct
21 Correct 1427 ms 294144 KB Output is correct
22 Correct 1439 ms 295416 KB Output is correct
23 Correct 1359 ms 289960 KB Output is correct
24 Correct 1289 ms 289620 KB Output is correct
25 Correct 1378 ms 290032 KB Output is correct
26 Correct 1342 ms 289332 KB Output is correct
27 Correct 1302 ms 288972 KB Output is correct
28 Correct 1363 ms 289796 KB Output is correct
29 Correct 1419 ms 294008 KB Output is correct
30 Correct 1338 ms 289208 KB Output is correct
31 Correct 1462 ms 293692 KB Output is correct
32 Correct 3321 ms 336660 KB Output is correct
33 Correct 2694 ms 334996 KB Output is correct
34 Correct 3254 ms 343188 KB Output is correct
35 Correct 3353 ms 340860 KB Output is correct
36 Correct 2725 ms 341900 KB Output is correct
37 Correct 3221 ms 343536 KB Output is correct
38 Correct 4522 ms 375708 KB Output is correct
39 Correct 4438 ms 375600 KB Output is correct
40 Correct 3712 ms 347880 KB Output is correct
41 Correct 4624 ms 398640 KB Output is correct
42 Correct 4661 ms 397624 KB Output is correct
43 Correct 4611 ms 397516 KB Output is correct
44 Correct 4269 ms 374876 KB Output is correct