oj.uz

Submission #1039669

# Submission time Handle Problem Language Result Execution time Memory
1039669 2024-07-31T07:18:28 Z BF001 Sails (IOI07_sails) C++17
100 / 100
 68 ms 3820 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define N 100005
#define int long long

int n, bit[N];

struct ii{
    int h, k;
    bool operator < (ii& o){
        if (h == o.h) return k > o.k;
        return h < o.h;
    }
};

void ud(int l, int r, int val){
    if (l > r) return;
    while (l < N){
        bit[l] += val;
        l += (l & (-l));
    }
    r++;
    while (r < N){
        bit[r] -= val;
        r += (r & (-r));
    }
}

int get(int pos){
    int rt = 0;
    while (pos >= 1){
        rt += bit[pos];
        pos -= (pos & (-pos));
    }
    return rt;
}
 
ii a[N];
int ma = 0;

int bin(int val, int ma){
    int l = 1, r = ma, rt = 0;
    while (l <= r){
        int mid = (l + r) >> 1;
        if (get(mid) >= val){
            rt = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return rt;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i].h >> a[i].k;
        ma = max(ma, a[i].h);
    }

    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++){
        int r = a[i].h;
        int l = a[i].h - a[i].k + 1;
        int x = get(l);
        int l1 = bin(x, a[i].h) + 1;
        int r1 = bin(x + 1, a[i].h) + 1;
        ud(l1, r, 1);
        //cout << l1 << " " << r  << " ";
        l1 = r1 + (a[i].k - (r - l1 + 1)) - 1;
       // cout << r1 << " " << l1 << "\n";
        ud(r1, l1, 1);
    }

    int res = 0;
    for (int i = 1; i <= ma; i++){
        int val = get(i);
        if (val <= 1) continue;
        val--;
        res += (val + 1) * val / 2;
    }

    cout << res;
 
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 0 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 0 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 5 ms 856 KB Output is correct
2 Correct 13 ms 2984 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3020 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3160 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3416 KB Output is correct
2 Correct 44 ms 3688 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3676 KB Output is correct
2 Correct 40 ms 3420 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 3820 KB Output is correct
2 Correct 35 ms 3672 KB Output is correct