Submission #1239879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239879		jerzyk	Meetings (IOI18_meetings)	C++20	100 / 100	1633 ms	358820 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 int II = 2'000'000'000;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<20;
int tab[N], ed[N][2], ran[N][2];
pair<int, int> rmq[N][20];

pair<int, int> que[N];
vector<int> wh[N];
ll answer[N];
pair<ll, ll> drz[2][2 * N];
ll lazd[2][2 * N];

int GetMax(int a, int b)
{
    int d = b - a + 1;
    int p = 31 - __builtin_clz(d);
    if(rmq[a][p].st >= rmq[b - (1<<p) + 1][p].st)
        return -rmq[a][p].nd;
    return -rmq[b - (1<<p) + 1][p].nd;
}

void Licz(int n)
{
    for(int i = n; i >= 1; --i)
    {
        rmq[i][0] = pair{tab[i], -i};
        for(int j = 1; i + (1<<j) - 1 <= n; ++j)
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<(j - 1))][j - 1]);
    }
    vector<int> cur;
    tab[0] = II; cur.pb(0);
    for(int i = 1; i <= n; ++i)
    {
        while(tab[cur.back()] < tab[i])
        {
            ed[i][0] = cur.back();
            cur.pop_back();
        }
        ed[cur.back()][1] = i;
        cur.pb(i);
    }
}

inline void Push(int r, int v)
{
    for(int s = v * 2; s <= v * 2 + 1; ++s)
    {
        lazd[r][s] += lazd[r][v];
        drz[r][s].nd += lazd[r][v];
    }
    lazd[r][v] = 0LL;
}

void Add(int r, int v, int p, int k, int pz, int kz, ll x)
{
    if(pz > kz) return;
    if(p > kz || k < pz) return;
    if(p >= pz && k <= kz)
    {
        lazd[r][v] += x;
        drz[r][v].nd += x;
        return;
    }
    Add(r, v * 2, p, (p + k) / 2, pz, kz, x);
    Add(r, v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
}

void Upd(int r, int v, int p, int k, pair<ll, ll> x)
{
    if(v < N) Push(r, v);

    if(x <= drz[r][v])
        swap(x, drz[r][v]);
    ll pos = (p + k) / 2;
    if(x.st * pos + x.nd < drz[r][v].st * pos + drz[r][v].nd)
    {
        swap(drz[r][v], x);
        if(v < N)
            Upd(r, v * 2 + 1, (p + k) / 2 + 1, k, x);
    }else
    {
        if(v < N)
            Upd(r, v * 2, p, (p + k) / 2, x);
    }
}


void Change(int r, int v, int p, int k, int pz, int kz, pair<ll, ll> x)
{
    if(pz > kz) return;
    if(p > kz || k < pz) return;
    if(p >= pz && k <= kz)
    {
        Upd(r, v, p, k, x);
        return;
    }
    Push(r, v);
    Change(r, v * 2, p, (p + k) / 2, pz, kz, x);
    Change(r, v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
}

ll Query(int r, int v)
{
    ll pos = v;
    v += N;
    ll ans = I;
    while(v > 0)
    {
        ans += lazd[r][v];
        ans = min(ans, drz[r][v].st * pos + drz[r][v].nd);
        
        v /= 2;
    }
    return ans;
}

void DFS(int v)
{
    ran[v][0] = v; ran[v][1] = v;
    for(int l = 0; l < 2; ++l)
        if(ed[v][l] != 0)
        {
            DFS(ed[v][l]);
            ran[v][l] = ran[ed[v][l]][l];
        }
    ll val = tab[v];
    // cout << "\nDFS " << v << " | " << ed[v][0] << " " << ed[v][1] << '\n';
    for(int l = 0; l < (int)wh[v].size(); ++l)
    {
        int a = que[wh[v][l]].st, b = que[wh[v][l]].nd;
        ll cur = Query(1, a) + (ll)(b - v + 1) * val;
        ll cur2 = Query(0, b) + (ll)(v - a + 1) * val;
        // cout << "Q: " << wh[v][l] << " " << cur << " " << cur2 << "\n";
        answer[wh[v][l]] = min(cur, cur2);
    }
    Add(0, 1, 0, N - 1, v, ran[v][1], val * (ll)(v - ran[v][0] + 1));
    Add(1, 1, 0, N - 1, ran[v][0], v, val * (ll)(ran[v][1] - v + 1));
    // cout << "XD: " << Query(1, 2) << "\n";
    if(v > ran[v][0])
    {
        ll cur = Query(0, v - 1);
        pair<ll, ll> a = pair{val, cur - (ll)(v - 1) * val};
        Change(0, 1, 0, N - 1, v, ran[v][1], a);
    }

    if(v < ran[v][1])
    {
        ll cur = Query(1, v + 1);
        pair<ll, ll> a = pair{-val, cur + (ll)(v + 1) * val};
        Change(1, 1, 0, N - 1, ran[v][0], v, a);
    }
    // cout << "XD: " << Query(1, 2) << "\n";
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) 
{
    for(int r = 0; r < 2; ++r)
        for(int i = 1; i < N; ++i)
            drz[r][i] = pair{0LL, I};
    int n = H.size(), q = L.size();
    for(int i = 1; i <= n; ++i) tab[i] = H[i - 1];
    Licz(n);
    for(int i = 1; i <= q; ++i)
    {
        que[i] = pair{L[i - 1] + 1, R[i - 1] + 1};
        int akt = GetMax(que[i].st, que[i].nd);
        wh[akt].pb(i);
    }
    int s = GetMax(1, n);
    
    DFS(s);
    vector<ll> ans;
    for(int i = 1; i <= q; ++i)
        ans.pb(answer[i]);
    return ans;
}

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