Submission #702402

#	Time	Username	Problem	Language	Result	Execution time	Memory
702402		thimote75	Sails (IOI07_sails)	C++14	100 / 100	395 ms	8100 KiB

sails

#include <bits/stdc++.h>

using namespace std;

#define num long long

struct SGD {
    num sum  = 0;
    num size = 1;

    num __l_value = 0;
};

struct SegTree {
    vector<SGD> tree;

    int size, start, height;

    SegTree (int ps) {
        size   = ps;
        height = ceil(log2(size));
        start  = 1 << height;

        tree.resize(start << 1);

        for (int i = start - 1; i >= 1; i --)
            tree[i].size = 2 * tree[i * 2].size;   
    }

    num _value (int index) {
        index += start;
        _update(index);

        return tree[index].sum;
    }
    void _update (int index) {
        if (index == 0) return ;
        _update (index >> 1);

        if (index < start) {
            int n0 = index << 1;
            int n1 = n0 + 1;

            tree[n0].__l_value += tree[index].__l_value;
            tree[n1].__l_value += tree[index].__l_value;
        }

        tree[index].sum += tree[index].size * tree[index].__l_value;
        tree[index].__l_value = 0;
    }

    void _modify (int index, int delta) {
        _update(index);
        tree[index].__l_value += delta;
    }
    void modify (int left, int right, int delta) {
        left  += start;
        right += start;

        while (left < right) {
            if ((left  & 1) == 1) _modify(left,  delta);
            if ((right & 1) == 0) _modify(right, delta);
        
            left  = (left  + 1) >> 1;
            right = (right - 1) >> 1;
        }

        if (left == right) _modify(left, delta);
    }

    num compute () {
        num result = 0;

        for (int index = 0; index < size; index ++) {
            num sum = _value(index);

            result += sum * (sum - 1);
        }

        return result >> 1;
    }

    int lower_bound (num value) { // S[i] < x
        int a = -1;
        int b = size;

        while (b - a > 1) {
            int c = (a + b) >> 1;
            if (_value(c) < value) b = c;
            else a = c;
        }

        return b;
    }
    int upper_bound (num value) { // S[i] <= x <=> S[i] < x + 1
        return lower_bound(value + 1);
    }

    void update_1 (int height, int count) {
        // add 1 to the { count } minimals in range [0, height[

        int start = height - count;
        int end   = height - 1;

        if (start != 0 && _value(start) == _value(start - 1)) {
            int right_start = lower_bound(_value(start));
            if (right_start > end) {
                int left_start = upper_bound(_value(start));
                modify(left_start, left_start + count - 1, 1);
                return ;
            }

            int count_left  = right_start - start;

            int left_start = upper_bound(_value(start));
            int left_end   = left_start + count_left - 1;

            start = right_start;
            modify(left_start, left_end, 1);
        }

        modify(start, end, 1);

        //for (int x = 0; x < size; x ++)
        //    cout << _value(x) << " ";
        //cout << endl;
    }
};

struct Sail {
    int height;
    int count;

    Sail (int ph, int pc) : height(ph), count(pc) {}

    bool operator< (const Sail &other) {
        if (height == other.height) return count < other.count;

        return height < other.height;
    }
};

int main () {
    int maxSailHeight = 0, nbSails = 0;
    cin >> nbSails;

    vector<Sail> sailArray;
    for (int idSail = 0; idSail < nbSails; idSail ++) {
        int h, c;
        cin >> h >> c;

        sailArray.push_back(Sail(h, c));
        maxSailHeight = max(maxSailHeight, h);
    }

    SegTree tree(maxSailHeight);
    sort(sailArray.begin(), sailArray.end());

    for (Sail &sail : sailArray)
        tree.update_1(sail.height, sail.count);

    cout << tree.compute();
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10