Submission #139283

#	Time	Username	Problem	Language	Result	Execution time	Memory
139283		fredbr	Meetings (IOI18_meetings)	C++17	17 / 100	117 ms	10148 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct Seg {
    struct Node {
        int l, r, tot, sz;

        static Node join(Node const& a, Node const& b) {
            Node ans = {a.l, 
                        b.r,
                        max({a.tot, b.tot, a.r+b.l}),
                        a.sz + b.sz};

            if (a.tot == a.sz) ans.l = a.tot + b.l;
            if (b.tot == b.sz) ans.r = b.tot + a.r;

            return ans;
        }
    };

    vector<Node> tree;
    vector<int> const& v;

    Seg(vector<int> const& v) : tree(v.size()*4), v(v) {
        build(0, 0, v.size()-1);
    }

    void build(int no, int l, int r) {
        if (l == r) {
            if (v[l] == 1) tree[no] = Node{1, 1, 1, 1};
            else tree[no] = Node{0, 0, 0, 1};
        }
        else {
            int m = (l+r)/2;

            build(no*2+1, l, m);
            build(no*2+2, m+1, r);
        
            tree[no] = Node::join(tree[no*2+1], tree[no*2+2]);
        }
    }

    Node get(int no, int l, int r, int a, int b) {
        if (a <= l and r <= b) return tree[no];
        else {
            int m = (l+r)/2;

            if (b <= m) return get(no*2+1, l, m, a, b);
            if (a > m) return get(no*2+2, m+1, r, a, b);

            return Node::join(get(no*2+1, l, m, a, b),
                              get(no*2+2, m+1, r, a, b));
        }
    }
};

vector<ll> minimum_costs(vector<int> h, vector<int> L,
                                        vector<int> R) {
    int n = h.size();

    Seg sg(h);

    int q = L.size();
    
    vector<ll> res;
    for (int at = 0; at < q; at++) {
        int l = L[at], r = R[at];

        Seg::Node ans = sg.get(0, 0, n-1, l, r);

        res.push_back(2ll*(r-l+1) - ans.tot);
    }

    return res;
}

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