제출 #585973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585973		jasmin	Meetings (IOI18_meetings)	C++14	0 / 100	5515 ms	2188 KiB

meetings

#include<bits/stdc++.h>
using namespace std;
#include<meetings.h>
const int inf=1e9;

struct segtree{
    vector<pair<int,int> > tree;

    segtree(int n, vector<int32_t>& a){
        tree.resize(n*4);
        build(0, n, 0, a);
    }

    pair<int,int> build(int l, int r, int v, vector<int32_t>& a){
        if(l+1==r){
            return tree[v]={a[l], l};
        }
        int m=l+(r-l)/2;
        return tree[v]=max(build(l, m, v*2+1, a), build(m, r, v*2+2, a));
    }

    pair<int,int> query(int l, int r, int v, int ql, int qr){
        if(qr<=l || r<=ql) return {0, -1};
        if(ql<=l && r<=qr) return tree[v];
        int m=l+(r-l)/2;
        return max(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
    }
};

long long cost(int l, int r, vector<int32_t>& h, segtree& seg, int n){
    if(r<l) return 0;
    if(l==r) return h[l];

    auto x=seg.query(0, n, 0, l, r+1);
    int mmax=x.first;
    int ind=x.second;

    int left=cost(l, ind-1, h, seg, n)+(r-ind+1)*mmax;
    int right=cost(ind+1, r, h, seg, n)+(ind-l+1)*mmax;
    return (long long)min(left, right);
}

vector<long long> minimum_costs(vector<int32_t> h, vector<int32_t> l, vector<int32_t> r){
   int n=h.size(); 
   int q=r.size();

   segtree seg(n, h);

   vector<long long> ans(q, inf);
    for(int i=0; i<q; i++){
        ans[i]=cost(l[i], r[i], h, seg, n);
    }
   return ans;
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n>> q;
    vector<int32_t> h(n);
    for(int i=0; i<n; i++){
        cin >> h[i];
    }
    vector<int32_t> l(q);
    vector<int32_t> r(q);
    for(int i=0; i<q; i++){
        cin >> l[i] >> r[i];
    }

    vector<int> ans=minimum_costs(h, l, r);
    for(auto e: ans){
        cout << e << "\n";
    }
}*/

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