oj.uz

Submission #941897

# Submission time Handle Problem Language Result Execution time Memory
941897 2024-03-09T16:16:49 Z codefox Sails (IOI07_sails) C++14
100 / 100
 124 ms 7000 KB 
#include<bits/stdc++.h> 

using namespace std;

#define pii pair<int, int>
#define lll long long
#pragma GCC optimize("O2")

int N = 1<<17;
vector<int> bpro(2*N, 0);
vector<int> bmin(2*N, 0);

void update(int curr, int l, int r, int ll, int rr, int p)
{
    if (l >= rr || r <= ll) 
    {
        bpro[curr]+=p;
        bmin[curr]+=p;
        return;
    }
    if (l >= ll && r <= rr)
    {
        bpro[curr]+=p+1;
        bmin[curr]+=p+1;
        return;
    }

    p += bpro[curr];
    bpro[curr] = 0;

    int m = (l+r)/2;
    update(curr*2, l, m, ll, rr, p);
    update(curr*2+1, m, r, ll, rr, p);
    bmin[curr] = min(bmin[curr*2], bmin[curr*2+1]);
}

int bsearch(int curr, int l, int r, int rr, int b, int p)
{
    if (bmin[curr]+p > b || l >= rr) 
    {
        bpro[curr]+=p;
        bmin[curr]+=p;
        return rr;
    }
    if (l+1 == r) 
    {
        bpro[curr]+=p;
        bmin[curr]+=p;
        return l;
    }
 
    p += bpro[curr];
    bpro[curr] = 0;
 
    int m = (l+r)/2;
    int mx = bsearch(curr*2, l, m, rr, b, p);
    if (mx == rr) mx = bsearch(curr*2+1, m, r, rr, b, p);
    else 
    {
        bpro[curr*2+1]+=p;
        bmin[curr*2+1]+=p;
    }
    bmin[curr] = min(bmin[curr*2], bmin[curr*2+1]);
    return mx;    
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n;
    cin >> n;
    vector<vector<int>> height(1e5+1);

    lll sol = 0;

    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        height[a].push_back(b);
    }

    for (int i = 1; i <= 1e5; i++)
    {
        for (int ele:height[i])
        {
            int ende = bmin[i-ele+N];
            int curr = i-ele+N;
            while (curr>1)
            {
                curr/=2;
                ende += bpro[curr];
            }
            int lower = bsearch(1, 0, N, i, ende, 0);
            int upper = bsearch(1, 0, N, i, ende-1, 0);
            update(1, 0, N, upper, i, 0);
            update(1, 0, N, lower, ele-(i-upper)+lower, 0);
        }
    }

    for (int i = 0; i < 1e5; i++)
    {
        lll h = bmin[i+N];
        int curr = i+N;
        while (curr>1)
        {
            curr/=2;
            h += bpro[curr];
        }
        sol += (h*(h-1))/2;
    }
    
    cout << sol << "\n";

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4696 KB Output is correct
2 Correct 3 ms 4700 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4712 KB Output is correct
2 Correct 4 ms 4696 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4700 KB Output is correct
2 Correct 4 ms 4700 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5060 KB Output is correct
2 Correct 30 ms 5392 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5724 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 5844 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 5504 KB Output is correct
2 Correct 85 ms 7000 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 6492 KB Output is correct
2 Correct 61 ms 6020 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 6996 KB Output is correct
2 Correct 91 ms 6236 KB Output is correct