Submission #1145065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145065		Issa	Meetings (IOI18_meetings)	C++20	100 / 100	4338 ms	307044 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e6 + 100;
const int maxl = 20;

int n;
ll a[maxn];
int lg[maxn];
int p[maxl][maxn];
ll d[maxn * 4];
ll t[maxn * 4];
bool c[maxn * 4];
vector<ll> ans;
vector<tuple<int, int, int>> g[maxn];
int C;

int f(int i, int j){
    if(C){
        if(a[i] >= a[j]) return i;
        return j;
    } else{
        if(a[i] > a[j]) return i;
        return j;
    }
} int mx(int l, int r){
    int k = lg[r - l + 1];
    return f(p[k][l], p[k][r-(1<<k)+1]);
}

void pre(int v, ll a, ll b, bool C){
    if(C) d[v] = t[v] = 0, c[v] = 1;
    d[v] += a; t[v] += b;
} void push(int v, int tl, int tr){
    if(tl == tr) return;
    int mid = (tl + tr) >> 1;
    pre(v<<1, d[v], t[v], c[v]);
    pre(v<<1|1, d[v] + (mid - tl + 1) * t[v], t[v], c[v]);
    d[v] = t[v] = c[v] = 0;
} void upd(int l, int r, ll a, ll b, bool c, int v = 1, int tl = 1, int tr = n){
    if(tl > r || tr < l) return;
    if(l <= tl && tr <= r) pre(v, a + (tl - l) * b, b, c);
    else{ push(v, tl, tr);
        int mid = (tl + tr) >> 1;
        upd(l, r, a, b, c, v<<1, tl, mid);
        upd(l, r, a, b, c, v<<1|1, mid+1, tr);
    }
} ll get(int i, int v = 1, int tl = 1, int tr = n){
    if(tl == tr) return d[v];
    else{ push(v, tl, tr);
        int mid = (tl + tr) >> 1;
        if(i <= mid) return get(i, v<<1, tl, mid);
        else return get(i, v<<1|1, mid+1, tr);
    }
}

void calc(int l = 1, int r = n){
    if(l > r) return;
    int v = mx(l, r);
    calc(l, v - 1); calc(v + 1, r);
    // cout << l << ' ' << r << ' ' << v << ":\n";
    for(auto [i, tl, tr]: g[v]){
        // cout << i << ' ' << tl << ' ' << tr << ' ' << get(tr) + (v - tl + 1) * a[v] << endl;
        ans[i] = min(ans[i], get(tr) + (v - tl + 1) * a[v]);
    }
    if(l < v) upd(v, v, get(v-1) + a[v], 0, 1);
    else upd(v, v, a[v], 0, 1);
    ll val = get(v), k = v;
    // cout << v << ' ' << l << ' ' << r << ":\n";
    for(int tl = v + 1, tr = r; tl <= tr;){
        int mid = (tl + tr) >> 1;
        // cout << mid << ' ' << val + (mid - v) * a[v] << ' ' << get(mid) + (v - l + 1) * a[v] << '\n';
        if(val + (mid - v) * a[v] > get(mid) + (v - l + 1) * a[v]) tr = mid - 1;
        else tl = mid + 1, k = mid;
    } upd(v + 1, k, val + a[v], a[v], 1);
    upd(k + 1, r, (v - l + 1) * a[v], 0, 0);
}

void calc(vector<int> A, vector<int> L, vector<int> R){
    fill(d, d + maxn * 4, 0);
    fill(t, t + maxn * 4, 0);
    fill(c, c + maxn * 4, 0);
    n = A.size();
    for(int i = 1; i <= n; i++){
        a[i] = A[i-1];
        p[0][i] = i;
        g[i].clear();
        if(i > 1) lg[i] = lg[i >> 1] + 1;
    } for(int k = 1; k < maxl; k++){
        for(int i = 1; i + (1<<k) - 1 <= n; i++){
            p[k][i] = f(p[k-1][i], p[k-1][i+(1<<(k-1))]);
        }
    } for(int i = 0; i < L.size(); i++){
        g[mx(L[i], R[i])].push_back({i, L[i], R[i]});
    }
    calc();
}
 
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    ans = vector<ll>(L.size(), 1e18);
    for(int &x: L) x++;
    for(int &x: R) x++;
    calc(H, L, R); C = 1;
    reverse(H.begin(), H.end());
    for(int &x: L) x = (n - x + 1);
    for(int &x: R) x = (n - x + 1);
    swap(L, R);
    calc(H, L, R);
    return ans;
}

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