Submission #817927

#	Time	Username	Problem	Language	Result	Execution time	Memory
817927		serifefedartar	Sails (IOI07_sails)	C++17	100 / 100	595 ms	4280 KiB

sails

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 7
#define MAXN 100005

vector<pair<int,int>> mast;
int sg[4*MAXN], lazy[4*MAXN];
void update(int k, int a, int b, int q_l, int q_r) {
    if (lazy[k]) {
        sg[k] += (b-a+1) * lazy[k];
        if (a != b) {
            lazy[2*k] += lazy[k];
            lazy[2*k+1] += lazy[k];
        }
        lazy[k] = 0;
    }

    if (q_l > b || q_r < a)
        return ;
    if (q_l <= a && b <= q_r) {
        sg[k] += b-a+1;
        if (a != b) {
            lazy[2*k]++;
            lazy[2*k+1]++;
        }
        return ;
    }
    update(2*k, a, (a+b)/2, q_l, q_r);
    update(2*k+1, (a+b)/2+1, b, q_l, q_r);
    sg[k] = sg[2*k] + sg[2*k+1];
}

int get(int k, int a, int b, int plc) {
    if (lazy[k]) {
        sg[k] += (b-a+1) * lazy[k];
        if (a != b) {
            lazy[2*k] += lazy[k];
            lazy[2*k+1] += lazy[k];
        }
        lazy[k] = 0;
    }

    if (plc < a || plc > b)
        return 0;
    if (a == b)
        return sg[k];
    return get(2*k, a, (a+b)/2, plc) + get(2*k+1, (a+b)/2+1, b, plc);
}

int main() {
    fast
    int N;
    cin >> N;

    mast = vector<pair<int,int>>(N);
    for (int i = 0; i < N; i++)
        cin >> mast[i].f >> mast[i].s;
    sort(mast.begin(), mast.end());

    for (int i = 0; i < N; i++) {
        int h = mast[i].f, k = mast[i].s;
        int left = 100001 - h;
        int plc = get(1, 1, 100000, left + k - 1);

        int L = left, R = 100000;
        int ans = -1; 
        while (R >= L) {
            int mid = L + (R-L)/2;
            if (get(1, 1, 100000, mid) < plc) {
                ans = mid;
                L = mid + 1;
            } else
                R = mid - 1;
        }

        L = left, R = 100000;
        int last_pos = -1;
        while (R >= L) {
            int mid = L + (R-L)/2;
            if (get(1, 1, 100000, mid) <= plc) {
                last_pos = mid;
                L = mid + 1;
            } else
                R = mid - 1;
        }

        if (ans != -1) {
            update(1, 1, 100000, left, ans);
            k -= ans - left + 1;
        }

        if (k)
            update(1, 1, 100000, last_pos - k + 1, last_pos);
    }

    ll ans = 0;
    for (int i = 1; i <= 100000; i++) {
        ll q = get(1, 1, 100000, i);
        ans += q * (q-1) / 2;
    }
    cout << ans << "\n";
}

• 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