Submission #1060175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060175		jerzyk	Meetings (IOI18_meetings)	C++14	19 / 100	5556 ms	13096 KiB

meetings

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
ll tab[N], l[N];
pair<pair<int, int>, int> que[N];
ll answer[N];

ll Ans(int a, int b)
{
    ll ans = I;
    vector<pair<ll, int>> kol;
    kol.pb(make_pair(I, a - 1));
    ll s = 0LL;
    l[a - 1] = 0LL;
    for(int i = a; i <= b; ++i)
    {
        while(kol.back().st <= tab[i])
        {
            int r = (int)kol.size() - 1;
            s -= (ll)(kol[r].nd - kol[r - 1].nd) * kol[r].st;
            kol.pop_back();
        }
        s += (ll)(i - kol.back().nd) * tab[i];
        kol.pb(make_pair(tab[i], i));
        l[i] = s;
    }
    kol.clear();
    kol.pb(make_pair(I, b + 1));
    s = 0LL;
    for(int i = b; i >= a; --i)
    {
        while(kol.back().st <= tab[i])
        {
            int r = (int)kol.size() - 1;
            s -= (ll)(kol[r - 1].nd - kol[r].nd) * kol[r].st;
            kol.pop_back();
        }
        s += (ll)(kol.back().nd - i) * tab[i];
        ans = min(l[i] - tab[i] + s, ans);
        kol.pb(make_pair(tab[i], i));
    }
    return ans;
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) 
{
    vector<ll> ans;
    int n = H.size(), q = L.size();
    for(int i = 1; i <= n; ++i) tab[i] = H[i - 1];
    for(int i = 1; i <= q; ++i)
        que[i] = make_pair(make_pair(L[i - 1] + 1, R[i - 1] + 1), i);
    for(int i = 1; i <= q; ++i)
        ans.pb(Ans(que[i].st.st, que[i].st.nd));
    return ans;
}

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