제출 #970538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
970538		jamesbamber	모임들 (IOI18_meetings)	C++17	36 / 100	748 ms	9820 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> quadratic(vector<int> H, vector<int> L, vector<int> R) {
    int Q = L.size();
    vector<ll> ans(Q);

    for(int q=0; q<Q; q++){
        int l = L[q], r = R[q]+1;
        int sz = r-l;
        vector<ll> pref(sz), suff(sz);
        stack<pair<ll,ll>> s;
        ll curr = 0;
        for(int i=l; i<r; i++){
            ll rm = 0;
            while(s.size() and s.top().first <= H[i]){
                rm += s.top().second;
                curr -= s.top().first*s.top().second;
                s.pop();
            }
            s.push({H[i], rm+1});
            curr += H[i]*(rm+1);
            pref[i-l] = curr;
        }

        while(s.size()) s.pop();
        curr = 0;
        for(int i=r-1; i>=l; i--){
            ll rm = 0;
            while(s.size() and s.top().first <= H[i]){
                rm += s.top().second;
                curr -= s.top().first*s.top().second;
                s.pop();
            }
            s.push({H[i], rm+1});
            curr += H[i]*(rm+1);
            suff[i-l] = curr;
        }

        ll mn = min(pref[sz-1], suff[0]);
        for(int i=1; i<sz; i++){
            mn = min(mn, pref[i-1]+suff[i]);
        }
        ans[q] = mn;
    }

    return ans;
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {

    int Q = L.size(); int N = H.size();
    if(N <= 5000 and Q <= 5000) return quadratic(H, L, R);

    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;
}

컴파일 시 표준 에러 (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: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40