Submission #960033

#	Time	Username	Problem	Language	Result	Execution time	Memory
960033		Pannda	Sails (IOI07_sails)	C++17	60 / 100	142 ms	7248 KiB

sails

#include <bits/stdc++.h>
using namespace std;

struct SegmentTree {
    struct Node {
        int mn = 0, mx = 0;
        int lazy = 0;
        void add(int delta) {
            mn += delta;
            mx += delta;
            lazy += delta;
        }
        void merge(Node &a, Node &b) {
            mn = min(a.mn, b.mn);
            mx = max(a.mx, b.mx);
            lazy = 0;
        }
    };

    int n;
    vector<Node> nodes;

    SegmentTree(int n) : n(n), nodes(4 * n) {}

    void down(int idx) {
        nodes[2 * idx + 1].add(nodes[idx].lazy);
        nodes[2 * idx + 2].add(nodes[idx].lazy);
        nodes[idx].lazy = 0;
    }

    void add(int ql, int qr, int delta) {
        auto dfs = [&](auto self, int idx, int l, int r) -> void {
            if (r <= ql || qr <= l) return;
            if (ql <= l && r <= qr) return nodes[idx].add(delta);
            down(idx);
            int m = (l + r) >> 1;
            self(self, 2 * idx + 1, l, m);
            self(self, 2 * idx + 2, m, r);
            nodes[idx].merge(nodes[2 * idx + 1], nodes[2 * idx + 2]);
        };
        dfs(dfs, 0, 0, n);
    }

    array<int, 2> getSame(int i) {
        auto dfs = [&](auto self, int idx, int l, int r) -> int {
            if (l + 1 == r) {
                return nodes[idx].mn;
            } else {
                down(idx);
                int m = (l + r) >> 1;
                if (i < m) return self(self, 2 * idx + 1, l, m);
                else return self(self, 2 * idx + 2, m, r);
            }
        };
        int v = dfs(dfs, 0, 0, n);
        auto dfs_left = [&](auto self, int idx, int l, int r) -> int {
            if (l + 1 == r) {
                return l;
            } else {
                down(idx);
                int m = (l + r) >> 1;
                if (nodes[2 * idx + 1].mn <= v) return self(self, 2 * idx + 1, l, m);
                return self(self, 2 * idx + 2, m, r);
            }
        };
        auto dfs_right = [&](auto self, int idx, int l, int r) -> int {
            if (l + 1 == r) {
                return l;
            } else {
                down(idx);
                int m = (l + r) >> 1;
                if (nodes[2 * idx + 2].mx >= v) return self(self, 2 * idx + 2, m, r);
                return self(self, 2 * idx + 1, l, m);
            }
        };
        return array<int, 2>{ dfs_left(dfs_left, 0, 0, n), dfs_right(dfs_right, 0, 0, n) + 1 };
    }

    vector<int> fullReport() {
        vector<int> res(n);
        auto dfs = [&](auto self, int idx, int l, int r) -> void {
            if (l + 1 == r) {
                res[l] = nodes[idx].mn;
            } else {
                down(idx);
                int m = (l + r) >> 1;
                self(self, 2 * idx + 1, l, m);
                self(self, 2 * idx + 2, m, r);
            }
        };
        dfs(dfs, 0, 0, n);
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<array<int, 2>> a(n);
    for (int i = 0; i < n; i++) {
        int h, k;
        cin >> h >> k;
        a[i] = {h, k};
    }
    sort(a.begin(), a.end());

    SegmentTree seg(n);
    for (int i = 0; i < n; i++) {
        auto [h, k] = a[i];
        auto [l, r] = seg.getSame(h - k);
        seg.add(r, h, +1);
        seg.add(l, l + (min(r, h) - (h - k)), +1);
    }

    vector<int> config = seg.fullReport();
    long long ans = 0;
    for (int x : config) {
        ans += 1LL * x * (x - 1) / 2;
    }
    cout << ans << '\n';
}

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