oj.uz

Submission #1038371

# Submission time Handle Problem Language Result Execution time Memory
1038371 2024-07-29T17:49:40 Z ArthuroWich Sails (IOI07_sails) C++17
100 / 100
 579 ms 6480 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int seg[4*200005], lazy[4*200005];
void lazypropagate(int n, int l, int r) {
    if (lazy[n]) {
        seg[n] += lazy[n];
        if (l != r) {
            lazy[2*n] += lazy[n];
            lazy[2*n+1] += lazy[n];
        }
        lazy[n] = 0;
    }
}
void update(int n, int l, int r, int a, int b, int v) {
    lazypropagate(n, l, r);
    if (b < l || r < a) {
        return;
    } else if (a <= l && r <= b) {
        lazy[n] += v;
        lazypropagate(n, l, r);
    } else {
        int m = (l+r)/2;
        update(2*n, l, m, a, b, v);
        update(2*n+1, m+1, r, a, b, v);
        seg[n] = min(seg[2*n], seg[2*n+1]);
    }
} 
int query(int n, int l, int r, int a, int b) {
    if (b < l || r < a) {
        return INT_MAX;
    }
    lazypropagate(n, l, r);
    if (a <= l && r <= b) {
        return seg[n];
    } else {
        int m = (l+r)/2;
        return min(query(2*n, l, m, a, b), query(2*n+1, m+1, r, a, b));
    }
}
int ithquery(int n, int l, int r, int i, int v) {
    lazypropagate(n, l, r);
    if (l == r) {
        return seg[n];
    } else {
        int m = (l+r)/2;
        if (l <= i && i <= m) {
            return ithquery(2*n, l, m, i, v);
        } else {
            return ithquery(2*n, m+1, r, i, v);
        }
    }
}
int search(int n, int h) {
    int l = 0, r = n;
    while(l < r) {
        int m = (l+r+1)/2, v;
        v = query(1, 0, 100000, 0, m);
        if (v > h) {
            l = m;
        } else {
            r = m-1;
        }
    }
    if (query(1, 0, 100000, 0, l) > h) {
        return l+1;
    } else {
        return l;
    }
}
void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> masts(n);
    for (auto &[h, k] : masts) {
        cin >> h >> k;
    }
    sort(masts.begin(), masts.end());
    for (auto [h, k] : masts) {
        if (h-k == 0) {
            update(1, 0, 100000, 0, h-1, 1);
            continue;
        }
        int v1 = query(1, 0, 100000, 0, h-k), v2 = query(1, 0, 100000, 0, h-k-1);;
        if (v1 != v2) {
            update(1, 0, 100000, h-k, h-1, 1);
            continue;
        }
        int ind1 = search(h-1, v1-1);
        int ind2 = search(h-1, v2);
        if (ind1 != h) {
            update(1, 0, 100000, ind1, h-1, 1);
            k -= h-ind1;
        }
        update(1, 0, 100000, ind2, ind2+k-1, 1);
    }
    int ans = 0;
    for (int i = 0; i <= 100000; i++) {
        int v = query(1, 0, 100000, i, i);
        v--;
        ans += v*(v+1)/2;
    }
    cout << ans << endl;
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--) {
        solve();
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4444 KB Output is correct
2 Correct 12 ms 524 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4444 KB Output is correct
2 Correct 19 ms 592 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 856 KB Output is correct
2 Correct 21 ms 4604 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1620 KB Output is correct
2 Correct 136 ms 1372 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 5664 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 3152 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 5712 KB Output is correct
2 Correct 388 ms 6480 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 5908 KB Output is correct
2 Correct 417 ms 5704 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 6080 KB Output is correct
2 Correct 430 ms 4344 KB Output is correct