Submission #1039669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039669		BF001	Sails (IOI07_sails)	C++17	100 / 100	68 ms	3820 KiB

sails

#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 / 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