제출 #982864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982864		mariaclara	Meetings (IOI18_meetings)	C++17	19 / 100	186 ms	3932 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 4e5+5, INF = 1e9;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

vector<int> h;

struct no{
    int l, r, ms, sum;
};

no operator + (no a, no b) {
    no c;
    c.l = max(a.l, a.sum + b.l);
    c.r = max(b.r, b.sum + a.r);
    c.ms = max({a.ms, b.ms, a.r + b.l});
    c.sum = a.sum + b.sum;
    return c;
}

no seg[4*MAXN];

void build(int node, int l, int r) {
    if(l == r) {
        seg[node].sum = h[l];
        seg[node].l = seg[node].r = seg[node].ms = max(0,h[l]);
        return;
    }
    int mid = (l+r)/2;
    build(2*node, l, mid);
    build(2*+node+1, mid+1, r);
    seg[node] = seg[2*node] + seg[2*node+1];
}

no query(int node, int l, int r, int p, int q) {
    if(r < p or q < l) return {-INF, -INF, -INF, -INF};
    if(p <= l and r <= q) return seg[node];
    int mid = (l+r)/2;
    return query(2*node, l, mid, p, q) + query(2*node+1, mid+1, r, p, q);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int N = sz(H), Q = sz(L), maxval = 0;

    for(int i = 0; i < N; maxval = max(maxval, H[i]), i++)
        if(H[i] == 1) h.pb(1);
        else h.pb(-N);

    if(maxval > 2) {
        vector<ll> ans(Q,1e15), p(N);
        vector<int> v(N);

        for(int i = 0; i < N; i++) {
            v[i] = H[i];

            for(int j = i-1; j >= 0; j--)
                v[j] = max(v[j+1], H[j]);
            for(int j = i+1; j < N; j++)
                v[j] = max(v[j-1], H[j]);
            
            p[0] = v[0];
            for(int j = 1; j < N; j++) p[j] = p[j-1] + v[j];

            for(int j = 0; j < Q; j++)
                ans[j] = min(ans[j], p[R[j]] - p[L[j]] + v[L[j]]);
        }

        return ans;
    }
    else {
        build(1, 0, N-1);

        vector<ll> ans(Q);
        for(int i = 0; i < Q; i++) {
            int k = query(1, 0, N-1, L[i], R[i]).ms;
            ans[i] = k + (R[i] - L[i] + 1)*2;
        }

        return ans;
    }
}

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