Submission #384983

#	Time	Username	Problem	Language	Result	Execution time	Memory
384983		LucaDantas	Meetings (IOI18_meetings)	C++17	0 / 100	42 ms	53612 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
 
using ll = long long;
using pii = pair<ll,ll>;
 
#define a first
#define b second
#define pb push_back
#define all(a) (a).begin(), (a).end()
 
constexpr int maxn = 2e5+10;
 
struct Line {
    mutable ll k, m, p;
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(ll x) const { return p < x; }
};
 
struct LineContainer : multiset<Line, less<>> {
    static const ll inf = 0x3f3f3f3f3f3f3f3f;
    ll div(ll a, ll b) {
        return a / b - ((a ^ b) < 0 && a % b); }
    bool isect(iterator x, iterator y) {
        if (y == end()) return x->p = inf, 0;
        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(ll k, ll m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    ll query(ll x) {
        if(empty()) return 0ll;
        assert(!empty());
        auto l = *lower_bound(x);
        return l.k * x + l.m;
    }
};
 
struct SegmentTree
{
    LineContainer tree[4*maxn];
    void upd(int node, int i, int j, int l, int r, const pii& L) {
        if(i > r || j < l) return;
        if(i >= l && j <= r) return (void)(tree[node].add(L.a, L.b));
        int m = (i+j) >> 1;
        upd(node<<1, i, m, l, r, L);
        upd(node<<1|1, m+1, j, l, r, L);
    }
    ll query(int node, int i, int j, int pos, ll x) {
        if(i == j) return tree[node].query(x);
        int m = (i+j) >> 1;
        if(pos <= m) return max(tree[node].query(x), query(node<<1, i, m, pos, x));
        return max(tree[node].query(x), query(node<<1|1, m+1, j, pos, x));
    }
    void clear() { for(int i = 0; i < 4*maxn; i++) tree[i].clear(); }
} seg;
 
struct SegmentTreeNormal
{
    ll tree[4*maxn];
    void upd(int node, int i, int j, int pos, ll v, bool set = 0) {
        if(i == j) return (void)(tree[node] = set?v:max(tree[node], v));
        int m = (i+j) >> 1;
        if(pos <= m) upd(node<<1, i, m, pos, v, set);
        else upd(node<<1|1, m+1, j, pos, v, set);
        tree[node] = max(tree[node<<1], tree[node<<1|1]);
    }
    ll query(int node, int i, int j, int l, int r) {
        if(i > r || j < l) return 0;
        if(i >= l && j <= r) return tree[node];
        int m = (i+j) >> 1;
        ll ans = query(node<<1, i, m, l, r);
        ans = max(ans, query(node<<1|1, m+1, j, l, r));
        return ans;
    }
    void clear() { memset(tree, 0, sizeof tree); }
} seg2, seg3;
 
struct Query
{
    int l, r;
} queries[maxn], itv[maxn];
 
struct Event
{
    int t, x, id;
    bool operator<(Event e) {
        if(x == e.x) return t < e.t;
        return x < e.x;
    }
};
 
vector<Event> events;
 
int a[maxn];
ll soma[maxn], suf[maxn];
 
multiset<int> ativos[maxn];
 
ll sum(int l, int r) { return soma[r] - soma[l-1]; }

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int n = (int)H.size(), q = (int)L.size();
	vector<ll> ans(q);
    for(int i = 0; i < n; i++)
    	a[i+1] = H[i];
    for(int i = 1; i <= n; i++)
        soma[i] = soma[i-1] + a[i];
    for(int i = n; i >= 1; i--)
        suf[i] = suf[i+1] + a[i];
 
    stack<int> st;
    for(int i = 1; i <= n; i++) {
        while(st.size() && a[i] <= a[st.top()]) {
            int id = st.top();
            st.pop();
            itv[id] = {st.size()?st.top()+1:1, i-1};
            events.pb({-1, st.size()?st.top()+1:1, id});
            events.pb({1, i-1, id});
        }
        st.push(i);
    }
    while(st.size()) {
        int id = st.top();
        st.pop();
        itv[id] = {st.size()?st.top()+1:1, n};
        events.pb({-1, st.size()?st.top()+1:1, id});
        events.pb({1, n, id});
    }
 
    for(int i = 0; i < q; i++) {
    	queries[i].l = L[i], queries[i].r = R[i];
        events.pb({2, queries[i].r, i});
    }
 
    sort(all(events));
 
    for(auto& e : events) {
        auto [t, r, id] = e;
        if(t == -1) {
            int l = itv[id].l;
            ativos[l].insert(a[id]);
            seg3.upd(1, 1, n, l, *ativos[l].rbegin(), 1);
        }
        if(t == 1) {
            int l = itv[id].l;
 
            ativos[l].erase(ativos[l].find(a[id]));
            seg3.upd(1, 1, n, l, ativos[l].size()?*ativos[l].rbegin():0, 1);
 
            pii reta = {-a[id], a[id] * soma[r]};
            seg.upd(1, 1, n, l, r, reta);
 
            seg2.upd(1, 1, n, l, 1ll*a[id]*sum(l, r));
 
            e.x = -l + n + 1;
        }
        if(t == 2) {
            int l = queries[id].l;
            ans[id] = max(ans[id], seg.query(1, 1, n, l, soma[l-1]));
 
            ans[id] = max(ans[id], seg2.query(1, 1, n, l, r));
 
            ans[id] = max(ans[id], seg3.query(1, 1, n, 1, l) * sum(l, r));
 
            e.x = -l + n + 1;
        }
    }
 
    seg.clear();
    seg2.clear();
 
    sort(all(events));
 
    for(auto& e : events) {
        auto [t, r, id] = e;
        if(t == 1) {
            int l = n+1 - itv[id].r;
            pii reta = {-a[id], a[id] * suf[n+1-r]};
            seg.upd(1, 1, n, l, r, reta);
            e.x = itv[id].r;
        }
        if(t == 2) {
            int l = n+1 - queries[id].r;
            ans[id] = max(ans[id], seg.query(1, 1, n, l, suf[n+1-(l-1)]));
            e.x = itv[id].r;
        }
    }
 
    // for(int i = 0; i < q; i++)
    //     printf("%lld\n", ans[i]);
    return ans;
}

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