oj.uz

Submission #648858

# Submission time Handle Problem Language Result Execution time Memory
648858 2022-10-08T14:38:52 Z vladutpiele Sails (IOI07_sails) C++17
100 / 100
 402 ms 7060 KB 
#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.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 2 ms 308 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 17 ms 4448 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1448 KB Output is correct
2 Correct 71 ms 1088 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 2116 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 3628 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 6348 KB Output is correct
2 Correct 294 ms 6452 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 6816 KB Output is correct
2 Correct 210 ms 5644 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 7060 KB Output is correct
2 Correct 244 ms 3880 KB Output is correct