oj.uz

Submission #1049582

# Submission time Handle Problem Language Result Execution time Memory
1049582 2024-08-09T00:05:35 Z ThegeekKnight16 Sails (IOI07_sails) C++17
100 / 100
 57 ms 2648 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
array<ll, MAXN> bit;

void update(int id, int val)
{
    while (id < MAXN)
    {
        bit[id] += val;
        id += id&-id;
    }
}

ll query(int id)
{
    ll resp = 0;
    while (id > 0)
    {
        resp += bit[id];
        id -= id&-id;
    }
    return resp;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<pair<int, int>> v(N);
    for (auto &[H, K] : v) cin >> H >> K;
    sort(v.begin(), v.end());
    int bitFirstId = MAXN-1;
    for (auto [H, K] : v)
    {
        bitFirstId = MAXN-H;
        int biggestUpd = query(bitFirstId+K-1);
        if (query(bitFirstId) != biggestUpd)
        {
            int ini = bitFirstId, fim = MAXN-1;
            while (ini < fim)
            {
                int m = (ini + fim + 1) >> 1;
                if (query(m) < biggestUpd) ini = m;
                else fim = m-1;
            }
            update(bitFirstId, +1); update(ini+1, -1);
            K -= (ini - bitFirstId + 1);
        }
        int ini = bitFirstId, fim = MAXN-1;
        if (query(MAXN-1) == biggestUpd) ini = fim = MAXN;
        while (ini < fim)
        {
            int m = (ini + fim) >> 1;
            if (query(m) > biggestUpd) fim = m;
            else ini = m+1;
        }
        update(fim-K, +1); update(fim, -1);
    }
    ll resp = 0;
    for (int i = 1; i < MAXN; i++)
    {
        ll x = query(i);
        resp += (x * (x-1LL))/2LL;
    }
    cout << resp << '\n';
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 12 ms 832 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 804 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1116 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1796 KB Output is correct
2 Correct 41 ms 2648 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1876 KB Output is correct
2 Correct 28 ms 2384 KB Output is correct

Subtask #11
10.0 / 10.0

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