oj.uz

Submission #484786

# Submission time Handle Problem Language Result Execution time Memory
484786 2021-11-05T13:18:33 Z Alexandruabcde Sails (IOI07_sails) C++14
100 / 100
 90 ms 3000 KB 
#include <bits/stdc++.h>
#define ub(x) (x&(-x))

using namespace std;

constexpr int NMAX = 1e5 + 5;
typedef pair <int, int> PII;
typedef long long LL;

int N;

PII a[NMAX];
LL aib[NMAX];

void Update (int pos, int val) {
    for (int i = pos; i <= a[N].first; i += ub(i))
        aib[i] += val;
}

void UpdateInterval (int a, int b, int val) {
    Update(a, val);
    Update(b+1, -val);
}

LL Query (int pos) {
    LL S = 0;
    for (int i = pos; i > 0; i -= ub(i))
        S += aib[i];

    return S;
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 1; i <= N; ++ i )
        cin >> a[i].first >> a[i].second;

    sort(a+1, a+N+1);
}

void Solve () {
    for (int i = 1; i <= N; ++ i ) {
        int value = Query(a[i].first - a[i].second + 1);
        int ans_st = a[i].first - a[i].second + 1;
        int ans_dr = a[i].first - a[i].second + 1;

        int st = 1, dr = a[i].first - a[i].second + 1;

        while (st <= dr) {
            int mij = (st + dr) / 2;
            int x = Query(mij);

            if (x == value) {
                ans_st = mij;
                dr = mij - 1;
            }
            else st = mij + 1;
        }

        st = a[i].first - a[i].second + 1;
        dr = a[i].first;
        while (st <= dr) {
            int mij = (st + dr) / 2;
            int x = Query(mij);

            if (x == value) {
                ans_dr = mij;
                st = mij + 1;
            }
            else dr = mij - 1;
        }

        if (ans_st == a[i].first - a[i].second + 1) {
            UpdateInterval(ans_st, a[i].first, 1);
            continue;
        }

        if (ans_dr < a[i].first)
            UpdateInterval(ans_dr+1, a[i].first, 1);

        UpdateInterval(ans_st, ans_st - (a[i].first - ans_dr) + a[i].second - 1, 1);
    }
}

void Write () {
    LL ans = 0;
    for (int i = 1; i <= a[N].first; ++ i ) {
        LL x = Query(i) - 1;

        ans += x * (x+1) / 2;
    }

    cout << ans << '\n';
}

int main () {
    Read();
    Solve();
    Write();

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 588 KB Output is correct
2 Correct 21 ms 884 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1100 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2544 KB Output is correct
2 Correct 70 ms 2488 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 2704 KB Output is correct
2 Correct 43 ms 2400 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 3000 KB Output is correct
2 Correct 57 ms 2460 KB Output is correct