Submission #611968

#	Time	Username	Problem	Language	Result	Execution time	Memory
611968		Jomnoi	모임들 (IOI18_meetings)	C++17	36 / 100	1296 ms	28300 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;

const int MAX_N = 75e4 + 5;
const long long INF = 1e18 + 7;

int N, Q;
long long H[MAX_N];
pair <int, int> table[MAX_N][20];
vector <int> graph[MAX_N];

struct A {
    int ans, pre, suf, mx;

    A() {}
    A(int a, int p, int s, int m) : ans(a), pre(p), suf(s), mx(m) {}

    A operator+(const A &o) const {
        int ans_, pre_, suf_, max_;
        ans_ = max({ans, o.ans, suf + o.pre});
        pre_ = max(pre, (mx == 1) * (pre + o.pre));
        suf_ = max(o.suf, (o.mx == 1) * (o.suf + suf));
        max_ = max(mx, o.mx);
        return {ans_, pre_, suf_, max_};
    }
}tree[4 * MAX_N];

void build(int idx, int l, int r) {
    if(l == r) {
        return void(tree[idx] = {H[l] == 1, H[l] == 1, H[l] == 1, H[l]});
    }

    int mid = (l + r) / 2;
    build(idx * 2, l, mid);
    build(idx * 2 + 1, mid + 1, r);
    tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

A query(int idx, int l, int r, int ql, int qr) {
    if(r < ql or qr < l) {
        return {0, 0, 0, 0};
    }
    if(ql <= l and r <= qr) {
        return tree[idx];
    }

    int mid = (l + r) / 2;
    return query(idx * 2, l, mid, ql, qr) + query(idx * 2 + 1, mid + 1, r, ql, qr);
}

pair <int, int> getMax(int l, int r) {
    int j = log2(r - l + 1);
    return max(table[l][j], table[r - (1<<j) + 1][j]);
}

int build_tree(int l, int r) {
    if(l > r) {
        return -1;
    }

    int u = getMax(l, r).second;
    int L = build_tree(l, u - 1);
    int R = build_tree(u + 1, r);
    if(L != -1) {
        graph[u].push_back(L);
    }
    if(R != -1) {
        graph[u].push_back(R);
    }
    return u;
}

long long dfs(int u, int l, int r, long long total = 0) {
    long long now = total + H[u] * (r - l + 1);
    for(auto v : graph[u]) {
        if(v < u) {
            now = min(now, dfs(v, l, u - 1, total + H[u] * (r - u + 1)));
        }
        else {
            now = min(now, dfs(v, u + 1, r, total + H[u] * (u - l + 1)));
        }
    }
    return now;
}

vector <long long> minimum_costs(vector <int> h, vector <int> L, vector <int> R) {
    N = h.size(), Q = L.size();
    vector <long long> C;
    for(int i = 1; i <= N; i++) {
        H[i] = h[i - 1];
    }
    for(int i = 0; i < Q; i++) {
        L[i]++, R[i]++;
    }

    if(N <= 5000 and Q <= 5000) {
        for(int i = 1; i <= N; i++) {
            table[i][0] = make_pair(H[i], i);
        }
        for(int j = 1; j < 20; j++) {
            for(int i = 1; i + (1<<j) - 1 <= N; i++) {
                table[i][j] = max(table[i][j - 1], table[i + (1<<(j - 1))][j - 1]);
            }
        }

        for(int i = 0; i < Q; i++) {
            for(int i = 1; i <= N; i++) {
                graph[i].clear();
            }
            C.push_back(dfs(build_tree(L[i], R[i]), L[i], R[i]));
        }
    }
    else {
        build(1, 1, N);
        for(int i = 0; i < Q; i++) {
            int maxseq1 = query(1, 1, N, L[i], R[i]).ans;
            C.push_back(2 * (R[i] - L[i] + 1 - maxseq1) + maxseq1);
        }
    }
    return C;
}

Compilation message (stderr)

meetings.cpp: In function 'void build(int, int, int)':
meetings.cpp:31:70: warning: narrowing conversion of 'H[l]' from 'long long int' to 'int' [-Wnarrowing]
   31 |         return void(tree[idx] = {H[l] == 1, H[l] == 1, H[l] == 1, H[l]});
      |                                                                   ~~~^

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