oj.uz

Submission #971799

# Submission time Handle Problem Language Result Execution time Memory
971799 2024-04-29T10:15:53 Z fve5 Meetings (IOI18_meetings) C++17
19 / 100
 559 ms 2340 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] = 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 448 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 348 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 448 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 348 KB Output is correct
10 Correct 158 ms 848 KB Output is correct
11 Correct 552 ms 864 KB Output is correct
12 Correct 149 ms 820 KB Output is correct
13 Correct 559 ms 852 KB Output is correct
14 Correct 73 ms 852 KB Output is correct
15 Correct 78 ms 780 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 18 ms 2340 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 448 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 348 KB Output is correct
10 Correct 158 ms 848 KB Output is correct
11 Correct 552 ms 864 KB Output is correct
12 Correct 149 ms 820 KB Output is correct
13 Correct 559 ms 852 KB Output is correct
14 Correct 73 ms 852 KB Output is correct
15 Correct 78 ms 780 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Incorrect 18 ms 2340 KB Output isn't correct
18 Halted 0 ms 0 KB -