Submission #594258

#	Time	Username	Problem	Language	Result	Execution time	Memory
594258		SlavicG	Meetings (IOI18_meetings)	C++17	36 / 100	703 ms	400240 KiB

meetings

#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()

const int N = 1e5 + 10;
struct node {
    int mx, suf, pref, l, r;
} t[4 * N];

node neutral = {-1, -1, -1, -1, -1};
node merge(node a, node b) {
    if(a.mx == -1) return b;
    if(b.mx == -1) return a;
    node c;
    c.l = a.l, c.r = b.r;
    c.mx = max({a.mx, b.mx, a.suf + b.pref});
    c.pref = a.pref;
    c.suf = b.suf;
    if(a.pref == a.r - a.l + 1) {
        c.pref = max(c.pref, a.pref + b.pref);
    }
    if(b.suf == b.r - b.l + 1) {
        c.suf = max(c.suf, b.suf + a.suf);
    }
    return c;
}
void build(int i, int l, int r, vector<int>& h) {
    if(l > r) return;
    if(l == r) {
        t[i].pref = t[i].mx = t[i].suf = (h[l] == 1);
        t[i].l = t[i].r = l;
        return;
    }
    int mid = l + r >> 1;
    build(2 * i, l, mid, h);
    build(2 * i + 1, mid + 1, r, h);
    t[i] = merge(t[2 * i], t[2 * i + 1]);
}
node query(int i, int l, int r, int tl, int tr) {
    if(l > tr || r < tl) return neutral;
    if(l >= tl && r <= tr) return t[i];
    int mid = l + r >> 1;
    return merge(query(2 * i, l, mid, tl, tr), query(2 * i + 1, mid + 1, r, tl, tr));
}
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
    for(int i = 0; i < 4 * N; ++i) t[i] = neutral;
    int q = l.size(), n = h.size();
    vector<ll> ans(q);

    build(1, 0, n - 1, h);
    if(n > 5000) {
        for(int i = 0; i < q; ++i) {
            node x = query(1, 0, n - 1, l[i], r[i]);
            ans[i] = x.mx + (r[i] - l[i] + 1 - x.mx) * 2;
        }
    } else {
        vector<vector<ll>> right(n, vector<ll>(n, 0)), left(n, vector<ll>(n, 0));
        for(int i = 0; i < n; ++i) {
            int mx = h[i];
            for(int r = i; r < n; ++r) {
                mx = max(mx, h[r]);
                right[i][r] += mx + (r > i ? right[i][r - 1] : 0);
            }
            mx = h[i];
            for(int l = i - 1; l >= 0; --l) {
                mx = max(mx, h[l]);
                left[i][l] += mx + left[i][l + 1];
            }
        }
        for(int i = 0; i < q; ++i) {
            ans[i] = LLONG_MAX;
            for(int j = l[i]; j <= r[i]; ++j) {
                ll valnow = right[j][r[i]] + left[j][l[i]];
                ans[i] = min(ans[i], valnow);
            }
        }
    }
    return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'void build(int, int, int, std::vector<int>&)':
meetings.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid = l + r >> 1;
      |               ~~^~~
meetings.cpp: In function 'node query(int, int, int, int, int)':
meetings.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid = l + r >> 1;
      |               ~~^~~

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