Submission #941896

#	Time	Username	Problem	Language	Result	Execution time	Memory
941896		codefox	Sails (IOI07_sails)	C++14	40 / 100	1091 ms	6744 KiB

sails

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10