Submission #941891

#	Time	Username	Problem	Language	Result	Execution time	Memory
941891		codefox	Sails (IOI07_sails)	C++14	40 / 100	1058 ms	3164 KiB

sails

#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 (stderr)

sails.cpp: In function 'int32_t main()':
sails.cpp:73:9: warning: unused variable 'left' [-Wunused-variable]
   73 |     int left = 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