oj.uz

Submission #934429

# Submission time Handle Problem Language Result Execution time Memory
934429 2024-02-27T10:12:12 Z thinknoexit Sails (IOI07_sails) C++17
100 / 100
 426 ms 3920 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
pair<int, int> a[100100];
int tree[400400], lazy[400400];
ll ans = 0;
void lzy(int now, int l, int r) {
    if (lazy[now] == 0) return;
    tree[now] += lazy[now];
    if (l != r) {
        lazy[2 * now] += lazy[now];
        lazy[2 * now + 1] += lazy[now];
    }
    lazy[now] = 0;
}
void update(int ql, int qr, int now = 1, int l = 1, int r = 100000) {
    lzy(now, l, r);
    if (l > qr || r < ql) return;
    if (ql <= l && r <= qr) {
        lazy[now]++;
        lzy(now, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(ql, qr, 2 * now, l, mid), update(ql, qr, 2 * now + 1, mid + 1, r);
    tree[now] = max(tree[2 * now], tree[2 * now + 1]);
}
int query(int v, int now = 1, int l = 1, int r = 100000) {
    lzy(now, l, r);
    if (l == r) return tree[now];
    int mid = (l + r) / 2;
    if (v <= mid) return query(v, 2 * now, l, mid);
    else return query(v, 2 * now + 1, mid + 1, r);
}
void print(int now = 1, int l = 1, int r = 100000) {
    lzy(now, l, r);
    if (l == r) {
        if (l <= 4) cout << tree[now] << ' ';
        return;
    }
    int mid = (l + r) / 2;
    print(2 * now, l, mid);
    print(2 * now + 1, mid + 1, r);
}
void dfs(int now = 1, int l = 1, int r = 100000) {
    lzy(now, l, r);
    if (l == r) {
        ans += 1ll * tree[now] * (tree[now] - 1) / 2;
        return;
    }
    int mid = (l + r) / 2;
    dfs(2 * now, l, mid);
    dfs(2 * now + 1, mid + 1, r);
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1;i <= n;i++) {
        int h = a[i].first, k = a[i].second;
        if (h == k) {
            update(1, h);
            continue;
        }
        int mn = query(h);
        int v = query(h - k + 1);
        int l = 1, r = h - k + 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (query(mid) == v) r = mid;
            else l = mid + 1;
        }
        int p = l;
        if (v != mn) {
            l = h - k + 2, r = h;
            while (l < r) {
                int mid = (l + r) / 2;
                if (query(mid) < v) r = mid;
                else l = mid + 1;
            }
            update(l, h);
            k -= h - l + 1;
        }
        if (k != 0) update(p, p + k - 1);
    }
    dfs();
    cout << ans;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1064 KB Output is correct
2 Correct 81 ms 1104 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1256 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 1872 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 3308 KB Output is correct
2 Correct 250 ms 3920 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 3116 KB Output is correct
2 Correct 121 ms 2644 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 3252 KB Output is correct
2 Correct 206 ms 1876 KB Output is correct