Submission #970537

#	Time	Username	Problem	Language	Result	Execution time	Memory
970537		jamesbamber	Meetings (IOI18_meetings)	C++17	17 / 100	70 ms	11768 KiB

meetings

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

typedef long long ll;

struct segment{
    struct node{
        int pref, suff, sz, mx;
        node(): pref(0), suff(0), mx(0), sz(0) {}
        node(int val): pref(val), suff(val), mx(val), sz(1) {}
        node(node a, node b) {
            pref = a.pref;
            if(a.mx == a.sz) pref = a.sz + b.pref;
            suff = b.suff;
            if(b.mx == b.sz) suff = b.sz + a.suff;
            sz = a.sz + b.sz;
            mx = max({a.mx, b.mx, a.suff + b.pref});
        }
    };  
    vector<node> tr;

    void build(int v, int l, int r, vector<int> &vec){
        if(r-l == 1){
            tr[v] = node(vec[l] == 1);
            return;
        }
        int m = (l+r)/2;
        build(2*v, l, m, vec);
        build(2*v+1, m, r, vec);
        tr[v] = node(tr[2*v], tr[2*v+1]);
        //cerr << v << " " << l << " " << r << " " << tr[v].mx << " " << tr[v].sz << " " << tr[v].pref << " " << tr[v].suff << endl;
    }

    segment(int sz, vector<int> &vec){
        tr.resize(4*sz);
        build(1, 0, sz, vec);
    }

    node query(int v, int l, int r, int ql, int qr){
        if(l >= qr  or r <= ql) return node();
        if(l >= ql and r <= qr) return tr[v];
        int m = (l+r)/2;
        return node(query(2*v, l, m, ql, qr), query(2*v+1, m, r, ql, qr));
    }
};

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

    segment st(N, H);

    for(int q=0; q<Q; q++){
        int l = L[q], r = R[q]+1;
        ans[q] = 2*(r-l) - st.query(1, 0, N, l, r).mx;
    }
    return ans;
}

Compilation message (stderr)

meetings.cpp: In constructor 'segment::node::node()':
meetings.cpp:9:29: warning: 'segment::node::mx' will be initialized after [-Wreorder]
    9 |         int pref, suff, sz, mx;
      |                             ^~
meetings.cpp:9:25: warning:   'int segment::node::sz' [-Wreorder]
    9 |         int pref, suff, sz, mx;
      |                         ^~
meetings.cpp:10:9: warning:   when initialized here [-Wreorder]
   10 |         node(): pref(0), suff(0), mx(0), sz(0) {}
      |         ^~~~
meetings.cpp: In constructor 'segment::node::node(int)':
meetings.cpp:9:29: warning: 'segment::node::mx' will be initialized after [-Wreorder]
    9 |         int pref, suff, sz, mx;
      |                             ^~
meetings.cpp:9:25: warning:   'int segment::node::sz' [-Wreorder]
    9 |         int pref, suff, sz, mx;
      |                         ^~
meetings.cpp:11:9: warning:   when initialized here [-Wreorder]
   11 |         node(int val): pref(val), suff(val), mx(val), sz(1) {}
      |         ^~~~

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