oj.uz

Submission #941896

# Submission time Handle Problem Language Result Execution time Memory
941896 2024-03-09T16:15:13 Z codefox Sails (IOI07_sails) C++14
40 / 100
 1000 ms 6744 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);
    mx = min(mx, bsearch(curr*2+1, m, r, rr, b, 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 4700 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 4868 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1020 ms 4952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 5724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 5720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1050 ms 5468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 6488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 6744 KB Time limit exceeded
2 Halted 0 ms 0 KB -