Submission #603998

#	Time	Username	Problem	Language	Result	Execution time	Memory
603998		AlperenT	Meetings (IOI18_meetings)	C++17	19 / 100	148 ms	2776 KiB

meetings

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

using namespace std;

const long long INF = (long long)2e18 + 5;

long long n, q;

vector<long long> h, predp, sufdp, prenext, sufnext, ans; 

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

    h = {0};
    for(auto x : H) h.push_back(x);

    predp.assign(n + 5, 0), sufdp.assign(n + 5, 0), prenext.assign(n + 5, 0), sufnext.assign(n + 5, 0), ans.assign(q, INF);

    for(auto &x : l) x++;
    for(auto &x : r) x++;

    stack<pair<long long, long long>> stk;

    stk.push({INF, -INF});

    for(int i = 1; i <= n; i++){
        while(stk.top().first <= h[i]) stk.pop();

        prenext[i] = stk.top().second;

        stk.push({h[i], i});
    }

    stk = {};

    stk.push({INF, INF});

    for(int i = n; i >= 1; i--){
        while(stk.top().first <= h[i]) stk.pop();

        sufnext[i] = stk.top().second;

        stk.push({h[i], i});
    }

    if(n <= 5000 && q <= 5000){  // Subtask 1 & 2
        for(int qq = 0; qq < q; qq++){
            predp[l[qq] - 1] = sufdp[r[qq] + 1] = 0; 

            predp[l[qq]] = h[l[qq]];

            for(int i = l[qq] + 1; i <= r[qq]; i++){
                if(h[i] <= h[i - 1]) predp[i] = predp[i - 1] + h[i];
                else{
                    int prv = max(prenext[i], (long long)l[qq] - 1);

                    predp[i] = predp[prv] + 1ll * (i - prv) * h[i];
                }
            }

            sufdp[r[qq]] = h[r[qq]];

            for(int i = r[qq] - 1; i >= l[qq]; i--){
                if(h[i] <= h[i + 1]) sufdp[i] = sufdp[i + 1] + h[i];
                else{
                    int prv = min(sufnext[i], (long long)r[qq] + 1);

                    sufdp[i] = sufdp[prv] + 1ll * (prv - i) * h[i];
                }
            }

            for(int i = l[qq]; i <= r[qq]; i++) ans[qq] = min(ans[qq], predp[i] + sufdp[i] - h[i]);
        }
    }

    return ans;
}

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