Submission #594246

#	Time	Username	Problem	Language	Result	Execution time	Memory
594246		SlavicG	Meetings (IOI18_meetings)	C++17	0 / 100	1 ms	312 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];
        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) {
    int q = l.size(), n = h.size();
    vector<ll> ans(q);
    build(1, 0, n - 1, h);
    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;
    }
    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: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40