Submission #648858

#	Time	Username	Problem	Language	Result	Execution time	Memory
648858		vladutpiele	Sails (IOI07_sails)	C++17	100 / 100	402 ms	7060 KiB

sails

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int nmax = 100000;

int n;
struct elem
{
    int h, k;
    bool operator < (const elem &other) const
    {
        return h < other.h;
    }
};
elem v[nmax + 5];

int aint[4 * nmax + 5], lazy[4 * nmax + 5];

void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint[nod] = 0;
        return ;
    }
    int mid = (st + dr) >> 1;
    build(2 * nod, st, mid);
    build(2 * nod + 1, mid + 1, dr);
}

void update(int nod, int st, int dr, int l, int r, int val)
{
    if(st > dr)
    {
        return ;
    }
    if(lazy[nod] != 0)
    {
        aint[nod] += lazy[nod];
        if(st != dr)
        {
            lazy[2 * nod] += lazy[nod];
            lazy[2 * nod + 1] += lazy[nod];
        }
        lazy[nod] = 0;
    }
    if(st >= l && dr <= r)
    {
        aint[nod] += val;
        if(st != dr)
        {
            lazy[2 * nod] += val;
            lazy[2 * nod + 1] += val;
        }
        return ;
    }
    if(st > r || dr < l)
    {
        return ;
    }
    int mid = (st + dr) >> 1;
    update(2 * nod, st, mid, l, r, val);
    update(2 * nod + 1, mid + 1, dr, l, r, val);
}

int getVal(int nod, int st, int dr, int poz)
{
    if(lazy[nod] != 0)
    {
        aint[nod] += lazy[nod];
        if(st != dr)
        {
            lazy[2 * nod] += lazy[nod];
            lazy[2 * nod + 1] += lazy[nod];
        }
        lazy[nod] = 0;
    }
    if(st == dr)
    {
        return aint[nod];
    }
    int mid = (st + dr) >> 1;
    if(poz <= mid)
    {
        return getVal(2 * nod, st, mid, poz);
    }
    else
    {
        return getVal(2 * nod + 1, mid + 1, dr, poz);
    }
}

signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> v[i].h >> v[i].k;
    }
    sort(v + 1, v + n + 1);

    cout << '\n';
    cout << '\n';

    int hmax = v[n].h;
    build(1, 1, hmax);
    for(int i = 1; i <= n; i ++)
    {
        int h = v[i].h, k = v[i].k;
        int val = getVal(1, 1, hmax, h - k + 1);
        int st = 1, dr = h;
        int first = 0, last = 0;
        while(st <= dr)
        {
            int mid = (st + dr) >> 1;
            if(getVal(1, 1, hmax, mid) >= val)
            {
                last = mid;
                st = mid + 1;
            }
            else
            {
                dr = mid - 1;
            }
        }
        st = 1, dr = h;
        while(st <= dr)
        {
            int mid = (st + dr) >> 1;
            if(getVal(1, 1, hmax, mid) <= val)
            {
                dr = mid - 1;
                first = mid;
            }
            else
            {
                st = mid + 1;
            }
        }
        if(last < h)
        {
            update(1, 1, hmax, last + 1, h, 1);
            k -= (h - last);
            update(1, 1, hmax, first, first + k - 1, 1);
        }
        else
        {
            update(1, 1, hmax, first, first + k - 1, 1);
        }
    }
    int answer = 0;
    for(int i = 1; i <= hmax; i ++)
    {
        int v = getVal(1, 1, hmax, i);
        answer += v * (v - 1) / 2;
    }
    cout << answer << '\n';
    return 0;
}
/*
6
3 2
5 3
4 1
2 1
4 3
3 2
*/

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10