oj.uz

Submission #960045

# Submission time Handle Problem Language Result Execution time Memory
960045 2024-04-09T14:58:15 Z Pannda Sails (IOI07_sails) C++17
50 / 100
 1000 ms 1628 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;
//    }
//};

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 800 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 1032 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 1116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1030 ms 1372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 1628 KB Time limit exceeded
2 Halted 0 ms 0 KB -