oj.uz

Submission #941891

# Submission time Handle Problem Language Result Execution time Memory
941891 2024-03-09T16:11:21 Z codefox Sails (IOI07_sails) C++14
40 / 100
 1000 ms 3164 KB 
#include<bits/stdc++.h> 

using namespace std;

#define pii pair<int, int>
#define lll long long

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<pii> height(n);

    int left = 0;
    lll sol = 0;

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

    for (pii ele:height)
    {
        int h = ele.first;
        int c = ele.second;
        int ende = bmin[h-c+N];
        int curr = h-c+N;
        while (curr>1)
        {
            curr/=2;
            ende += bpro[curr];
        }
        int lower = bsearch(1, 0, N, h, ende, 0);
        int upper = bsearch(1, 0, N, h, ende-1, 0);
        update(1, 0, N, upper, h, 0);
        update(1, 0, N, lower, c-(h-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;
}

Compilation message

sails.cpp: In function 'int32_t main()':
sails.cpp:73:9: warning: unused variable 'left' [-Wunused-variable]
   73 |     int left = 0;
      |         ^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 2396 KB Output is correct
2 Correct 279 ms 2648 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1032 ms 2392 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 1058 ms 2652 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 1051 ms 2908 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 1034 ms 2904 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 1038 ms 3164 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 1027 ms 3160 KB Time limit exceeded
2 Halted 0 ms 0 KB -