oj.uz

Submission #948723

# Submission time Handle Problem Language Result Execution time Memory
948723 2024-03-18T12:38:01 Z MisterReaper Sails (IOI07_sails) C++17
100 / 100
 600 ms 4676 KB 
#include <bits/stdc++.h>
using i64 = long long;

constexpr int maxN = 1E5 + 5;

int tree[maxN * 4], lazy[maxN * 4];
void push(int node, int l, int r) {
    tree[node] += lazy[node] * (r - l + 1);
    if(l != r) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
}

void update(int node, int l, int r, int ql, int qr, int v) {
    push(node, l, r);
    if(ql <= l && r <= qr) {
        lazy[node] += v;
        push(node, l, r);
        return;
    } else if(r < ql || qr < l) {
        return;
    }

    int mid = (l + r) / 2;
    update(node * 2, l, mid, ql, qr, v);
    update(node * 2 + 1, mid + 1, r, ql, qr, v);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
void update(int l, int r, int v = 1) { update(1, 1, maxN - 1, l, r, v); }

int query(int node, int l, int r, int ql, int qr) {
    push(node, l, r);
    if(ql <= l && r <= qr) {
        return tree[node];
    } else if(r < ql || qr < l) {
        return 0;
    }

    int mid = (l + r) / 2;
    int g1 = query(node * 2, l, mid, ql, qr);
    int g2 = query(node * 2 + 1, mid + 1, r, ql, qr);
    return g1 + g2;
}
int query(int l, int r) { return query(1, 1, maxN - 1, l, r); }

void solve() {
    int n;
    std::cin >> n;

    std::vector<std::pair<int, int>> v(n);
    for(int i = 0; i < n; i++) {
        std::cin >> v[i].first >> v[i].second;
    }

    std::sort(v.begin(), v.end());

    auto print = [&]() -> void {
        for(int i = 1; i <= 10; i++) {
            std::cerr << query(i, i) << " \n"[i == 10];
        }
    };

    for(int i = 0; i < n; i++) {
        //print();
        auto [h, c] = v[i];
        int g = query(h - c + 1, h - c + 1), f = 1;
        {
            int l = 1, r = h;
            while(l <= r) {
                int mid = (l + r) / 2;
                if(query(mid, mid) <= g) {
                    f = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }

        int L = f;
        update(L, h);
        if(L == h - c + 1) {
            continue;
        }


        f = h + 1;
        {
            int l = 1, r = h;
            while(l <= r) {
                int mid = (l + r) / 2;
                if(query(mid, mid) <= g) {
                    f = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }

        int interval = h - L + 1;
        update(f - (interval - c), f - 1, -1);
        //std::cerr << L << " " << g << " :: " << f - (interval - c) << " " << f - 1 << "\n";
    }
    //print();

    i64 ans = 0;
    for(int i = 1; i < maxN; i++) {
        int g = query(i, i);
        ans += 1LL * g * (g - 1) / 2;
    }

    std::cout << ans << "\n";
    
    return;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1; //std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

Compilation message

sails.cpp: In function 'void solve()':
sails.cpp:59:10: warning: variable 'print' set but not used [-Wunused-but-set-variable]
   59 |     auto print = [&]() -> void {
      |          ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2908 KB Output is correct
2 Correct 17 ms 2904 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2908 KB Output is correct
2 Correct 18 ms 3164 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2908 KB Output is correct
2 Correct 18 ms 2908 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2904 KB Output is correct
2 Correct 24 ms 2908 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2900 KB Output is correct
2 Correct 138 ms 3660 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 3044 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 3188 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 3632 KB Output is correct
2 Correct 469 ms 4428 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 3728 KB Output is correct
2 Correct 570 ms 4392 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 3936 KB Output is correct
2 Correct 518 ms 4676 KB Output is correct