oj.uz

Submission #960048

# Submission time Handle Problem Language Result Execution time Memory
960048 2024-04-09T15:00:22 Z Pannda Sails (IOI07_sails) C++17
100 / 100
 143 ms 6968 KB 
#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(1e5 + 1);
    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5468 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5468 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5464 KB Output is correct
2 Correct 3 ms 5560 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5468 KB Output is correct
2 Correct 6 ms 5468 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5468 KB Output is correct
2 Correct 39 ms 5944 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5716 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5792 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 5988 KB Output is correct
2 Correct 100 ms 6896 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 6228 KB Output is correct
2 Correct 76 ms 6744 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 6196 KB Output is correct
2 Correct 112 ms 6968 KB Output is correct