Submission #1232393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232393		VMaksimoski008	Meetings (IOI18_meetings)	C++20	17 / 100	73 ms	14920 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct segment_tree {
    int n;
    vector<int> tree;

    segment_tree(int _n) : n(_n), tree(4*n) {}

    void update(int u, int tl, int tr, int p, int v) {
        if(tl == tr) {
            tree[u] = max(tree[u], v);
        } else {
            int tm = (tl + tr) / 2;
            if(p <= tm) update(2*u, tl, tm, p, v);
            else update(2*u+1, tm+1, tr, p, v);
            tree[u] = max( tree[2*u], tree[2*u+1] );
        }
    }

    int query(int u, int tl, int tr, int l, int r) {
        if(tl > r || l > tr) return 0;
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return max( query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r) );
    }

    void update(int p, int v) { update(1, 0, n-1, p, v); }
    int query(int l, int r) { return query(1, 0, n-1, l, r); }
};

vector<ll> minimum_costs(vector<int> a, vector<int> L, vector<int> R) {
    int q = L.size(), n = a.size();
    vector<ll> ans(q, 1e18);
    vector<int>  pref(n, -1), suf(n, n+1);

    int lst = -1;
    set<pair<int, int> > B;
    for(int i=0; i<n; i++) {
        if(a[i] == 1) {
            B.insert({ i, lst+1 });
            pref[lst+1] = max(pref[lst+1], i);
            suf[i] = min(suf[i], lst+1);
        } else if(a[i] == 2) {
            lst = i;
        }
    }

    for(int i=1; i<n; i++) pref[i] = max(pref[i-1], pref[i]);
    for(int i=n-2; i>=0; i--) suf[i] = min(suf[i+1], suf[i]);

    for(int i=0; i<q; i++) {
        if(L[i] > 0 && pref[L[i]-1] >= L[i]) {
            int len = min(R[i], pref[L[i]-1]) - L[i] + 1;
            ans[i] = min(ans[i], 2ll * (R[i] - L[i] + 1) - len);
        }

        if(R[i] < n - 1 && suf[R[i]+1] <= R[i]) {
            int len = R[i] - max(L[i], suf[R[i]+1]) + 1;
            ans[i] = min(ans[i], 2ll * (R[i] - L[i] + 1) - len);
        }
    }

    segment_tree sgt(n);
    vector<pair<int, int> > qus[n];
    for(int i=0; i<q; i++) qus[R[i]].push_back({ L[i], i });

    for(int i=0; i<n; i++) {
        while(!B.empty() && B.begin()->first == i) {
            sgt.update(B.begin()->second, i - B.begin()->second + 1);
            B.erase( B.begin() );
        }
        for(auto [l, id] : qus[i])
            ans[id] = min(ans[id], 2ll * (i - l + 1) - sgt.query(l, i));
    }

    return ans;
}

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