Submission #585977

#	Time	Username	Problem	Language	Result	Execution time	Memory
585977		jasmin	Meetings (IOI18_meetings)	C++14	19 / 100	5534 ms	5336 KiB

meetings

#include<bits/stdc++.h>
using namespace std;
#include<meetings.h>
#define int long long

const int inf=1e18;

struct sparsetable{
    int l=25;
    vector<vector<pair<int,int> > > table;

    sparsetable(int n, vector<int32_t>& a){
        table.assign(n, vector<pair<int,int> > (l, make_pair(0, -1)));
        for(int i=0; i<n; i++){
            table[i][0]={a[i], i};
        }
        for(int i=1; i<l; i++){
            for(int j=0; j+(1<<(i-1))<n; j++){
                table[j][i]=max(table[j][i-1], table[j+(1<<(i-1))][i-1]);
            }
        }
    }

    pair<int,int> query(int left, int right){
        int x=right-left;
        pair<int,int> ans={0, -1};
        for(int i=0; i<l; i++){
            if((x>>i)%2==1){
                ans=max(ans, table[left][i]);
                left+=(1<<i);
            }
        }
        return ans;
    }
    
};

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

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

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

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

   sparsetable sp(n, h);

   vector<int> ans(q, inf);
    for(int i=0; i<q; i++){
        ans[i]=cost(l[i], r[i], h, sp, 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: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40