Submission #960045

#	Time	Username	Problem	Language	Result	Execution time	Memory
960045		Pannda	Sails (IOI07_sails)	C++17	50 / 100	1061 ms	1628 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;
//    }
//};

struct SegmentTree { // ?
    int n;
    vector<int> a;

    SegmentTree(int n) : n(n), a(n, 0) {}

    void add(int ql, int qr, int delta) {
        if (ql >= qr) return;
//        assert(0 <= ql && qr <= n);
        for (int i = ql; i < qr; i++) {
            a[i] += delta;
        }
    }

    array<int, 2> getSame(int i) {
//        assert(0 < i && i < n);
        int l = i, r = i + 1;
        while (l > 0 && a[l - 1] == a[i]) l--;
        while (r < n && a[r] == a[i]) r++;
        return {l, r};
    }

    vector<int> fullReport() {
        return a;
    }
};

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: 0 / 10