제출 #817673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817673		serifefedartar	Sails (IOI07_sails)	C++17	5 / 100	538 ms	5908 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
#define int long long

vector<pair<int,int>> masts;
int sg[4*MAXN], lazy[4*MAXN];
void increment(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_r < a || q_l > b)
        return ;
    if (q_l <= a && b <= q_r) {
        sg[k] += b-a+1;
        if (a != b) {
            lazy[2*k]++;
            lazy[2*k+1]++;
        }
        return ;
    }
    increment(2*k, a, (a+b)/2, q_l, q_r);
    increment(2*k+1, (a+b)/2+1, b, q_l, q_r);
    sg[k] = sg[2*k] + sg[2*k+1];
}

ll query(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 (b < plc || a > plc)
        return 0;
    if (a == b)
        return sg[k];
    return query(2*k, a, (a+b)/2, plc) + query(2*k+1, (a+b)/2+1, b, plc);
}

signed main() {
    fast
    int N, H, K;
    cin >> N;

    masts = vector<pair<int,int>>(N);
    for (int i = 0; i < N; i++) {
        cin >> H >> K;
        masts[i] = {H, K};
    }
    sort(masts.begin(), masts.end());

    int left = 100001 - masts[0].f;
    for (int i = 0; i < N; i++) {
        left = 100001 - masts[i].f;
        int l = left, r = 100000;
        int last_zero = -1;
        while (l <= r) {
            int mid = l + (r-l)/2;
            if (query(1, 1, 100000, mid) == 0) {
                last_zero = mid;
                l = mid + 1;
            } else
                r = mid - 1;
        }

        int q = query(1, 1, 100000, 100000);
        int R = 100000, L = left;
        int ans = -1;
        while (R >= L) {
            int mid = L + (R-L)/2;
            if (query(1, 1, 100000, mid) != q) {
                ans = mid;
                L = mid + 1;
            } else
                R = mid - 1;
        }

        int need = masts[i].s;
        if (last_zero != -1) {
            increment(1, 1, 100000, max(left, last_zero - need + 1), last_zero);
            need -= last_zero - max(left, last_zero - need + 1) + 1;
        }

        if (need && ans != -1 && q != 1) {
            increment(1, 1, 100000, max(left, max(last_zero + 1, ans - need + 1)), ans);
            need -= ans - max(left, max(last_zero + 1, ans - need + 1)) + 1;
        }

        if (need)
            increment(1, 1, 100000, 100001 - need, 100000);
    }

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

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10