Submission #1073743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073743		shezitt	Meetings (IOI18_meetings)	C++14	0 / 100	5553 ms	2904 KiB

meetings

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

using ll = long long;

#define fore(a, b, c) for(int a=b; a<c; ++a)
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

using namespace std;

struct segtree {
    int n;
    vector<ll> T;
    segtree(int n) : n(n) {
        T.assign(4*n+2, 0);
    }

    void update(int i, int tl, int tr, int idx, int val){
        if(tl == tr){
            T[i] = val;
            return;
        }
        int tm = (tl + tr) / 2;
        if(idx <= tm){
            update(2*i+1, tl, tm, idx, val);
        } else {
            update(2*i+2, tm+1, tr, idx, val);
        }
        T[i] = max(T[2*i+1], T[2*i+2]);
    }
    void update(int idx, int val){
        update(0, 0, n-1, idx, val);
    }

    ll query(int i, int tl, int tr, int l, int r){
        if(l <= tl && tr <= r){
            return T[i];
        }  
        if(r < tl or tr < l){
            return 0;
        }
        int tm = (tl + tr) / 2;
        ll p1 = query(2*i+1, tl, tm, l, r);
        ll p2 = query(2*i+2, tm+1, tr, l, r);
        return max(p1, p2);
    }
    ll query(int l, int r){
        return query(0, 0, n-1, min(l,r), max(l,r));
    }

};

std::vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int Q = L.size();
    vector<ll> C(Q);

    int N = 0;

    for (int j = 0; j < Q; ++j) {
        N = max(N, R[j]);
    }

    N++;
    assert(N<=3000);

    segtree T(N);
    for(int i=0; i<N; ++i){
        T.update(i, H[i]);
    }

    for(int j=0; j<Q; ++j){
        int l = L[j], r = R[j];

        ll ans = 4e18;
        for(int x=l; x<=r; ++x){
            ll cur = 0;
            for(int i=l; i<=r; ++i){
                cur += T.query(i, x);
            }
            ans = min(ans, cur);
        }

        C[j] = ans;

    }

  
    return C;
}

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