oj.uz

Submission #971809

# Submission time Handle Problem Language Result Execution time Memory
971809 2024-04-29T10:43:03 Z fve5 Meetings (IOI18_meetings) C++17
19 / 100
 557 ms 2396 KB 
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;

struct Info {
    int len, pref, suff, sub;
    Info(int len, int pref, int suff, int sub) : len(len), pref(pref), suff(suff), sub(sub) { }
    Info(int val) : Info(1, !val, !val, !val) { }
    Info() : Info(1, 0, 0, 0) { }
};

Info merge(const Info &a, const Info &b) {
    return {a.len + b.len, a.pref + (a.pref == a.len) * b.pref , b.suff + (b.suff == b.len) * a.suff, max({a.sub, b.sub, a.suff + b.pref})};
}

struct SegTree {
    vector<Info> arr;
    int s;

    Info query(int l, int r) {
        Info ans_l, ans_r;
        for (l += s, r += s; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ans_l = merge(ans_l, arr[l++]);
            if (r & 1) ans_r = merge(arr[--r], ans_r);
        }
        return merge(ans_l, ans_r);
    }

    SegTree(int N, const vector<int> &a) {
        s = 1 << (int)ceil(log2(N));
        arr.resize(2 * s);

        for (int i = 0; i < N; i++) arr[i + s] = Info(a[i]);
        for (int i = s - 1; i; i--) arr[i] = merge(arr[2 * i], arr[2 * i + 1]);
    }
};

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int N = H.size();
    int Q = L.size();
    
    vector<long long> ans(Q);

    if (Q <= 5000 && N <= 5000) {
        for (int i = 0; i < Q; i++) {
            vector<long long> cost_l(R[i] - L[i] + 2), cost_r(R[i] - L[i] + 2);

            stack<pair<int, int>> st;
            st.emplace(2e9, R[i] - L[i] + 1);
            for (int j = R[i] - L[i]; j >= 0; j--) {
                while (st.top().first <= H[j + L[i]]) st.pop();

                cost_r[j] = cost_r[st.top().second] + (long long)H[j + L[i]] * (st.top().second - j);
                st.emplace(H[j + L[i]], j);
            }

            while (!st.empty()) st.pop();

            st.emplace(2e9, 0);
            for (int j = 0; j <= R[i] - L[i]; j++) {
                while (st.top().first <= H[j + L[i]]) st.pop();

                cost_l[j + 1] = cost_l[st.top().second] + (long long)H[j + L[i]] * (j + 1 - st.top().second);
                st.emplace(H[j + L[i]], j + 1);
            }

            ans[i] = 1e18;
            for (int j = 0; j <= R[i] - L[i]; j++) {
                ans[i] = min(ans[i], cost_l[j + 1] + cost_r[j] - H[j + L[i]]);
            }
        }
    } else {
        SegTree segtree(N, H);
        for (int i = 0; i < Q; i++) {
            ans[i] = 2 * (R[i] - L[i] + 1) - segtree.query(L[i], R[i] + 1).sub;
        }
    }

    return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 153 ms 808 KB Output is correct
11 Correct 557 ms 792 KB Output is correct
12 Correct 147 ms 800 KB Output is correct
13 Correct 556 ms 788 KB Output is correct
14 Correct 72 ms 868 KB Output is correct
15 Correct 78 ms 808 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 18 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 18 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 153 ms 808 KB Output is correct
11 Correct 557 ms 792 KB Output is correct
12 Correct 147 ms 800 KB Output is correct
13 Correct 556 ms 788 KB Output is correct
14 Correct 72 ms 868 KB Output is correct
15 Correct 78 ms 808 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 18 ms 2396 KB Output isn't correct
18 Halted 0 ms 0 KB -