oj.uz

Submission #449815

# Submission time Handle Problem Language Result Execution time Memory
449815 2021-08-02T08:24:46 Z prvocislo Sails (IOI07_sails) C++17
100 / 100
 72 ms 4636 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;

const int maxn = 1e5 + 5;
int d[maxn], H = 0; // rozdiel oproti predoslemu, posledny aktivny stlpec
set<int> b;
void add(int l, int r) // chceme pridat l a r vratane
{
    if (r < l) return;
    d[l]++, d[r + 1]--;
    if (d[l] == 0) b.erase(l);
    if (d[r + 1] < 0) b.insert(r + 1);
}
struct mast { int h, k; } ship[maxn];
bool cmp(const mast& a, const mast& b) { return a.h < b.h; }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> ship[i].h >> ship[i].k;
    sort(ship, ship + n, cmp);
    b.insert(1);
    //cout << "\n";
    for (int i = 0; i < n; i++)
    {
        if (H != ship[i].h)
        {
            if (H && d[H + 1] == 0) b.erase(H + 1);
            H = ship[i].h;
            b.insert(H + 1);
        }
        int l = H - ship[i].k + 1;
        int l1 = *b.lower_bound(l), r1 = H;
        int len = ship[i].k - max(0, r1 - l1 + 1); 
        int l2 = *prev(b.upper_bound(l)), r2 = l2 + len - 1;
        add(l1, r1);
        add(l2, r2);
        /*for (int i = 1, val = d[1]; i <= H; val += d[++i])
            cout << val << " ";
        cout << "\n";*/
    }
    ll ans = 0;
    for (int i = 1, val = d[1]; i <= H; val += d[++i])
    {
        ans += val * 1ll * (val - 1) / 2ll;
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 588 KB Output is correct
2 Correct 14 ms 844 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2376 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1828 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2372 KB Output is correct
2 Correct 47 ms 2928 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 4636 KB Output is correct
2 Correct 31 ms 1948 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 3276 KB Output is correct
2 Correct 39 ms 2248 KB Output is correct