Submission #1249196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249196		1ncogn1to	Sails (IOI07_sails)	C++20	0 / 100	66 ms	2632 KiB

sails

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Segment tree trzymający informację, czy w danym przedziale
// jest jakikolwiek delta[i] != 0. Pozwala na:
// 1) punktową aktualizację delta[pos] += val
// 2) zapytanie: pozycja ostatniego niezerowego elementu <= x
// 3) zapytanie: pozycja pierwszego niezerowego elementu >= x
struct SegTree {
    int n;
    vector<bool> tree;
    SegTree(int _n): n(_n) {
        tree.assign(4*n, false);
    }
    void update(int idx, int l, int r, int pos, bool has) {
        if (l == r) {
            tree[idx] = has;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(idx<<1, l, mid, pos, has);
        else           update(idx<<1|1, mid+1, r, pos, has);
        tree[idx] = tree[idx<<1] | tree[idx<<1|1];
    }
    // public wrapper
    void update(int pos, bool has) {
        update(1, 0, n-1, pos, has);
    }
    // znajdź ostatnie delta!=0 w [ql..qr], lub -1 jeśli brak
    int find_last(int idx, int l, int r, int ql, int qr) {
        if (ql>qr || !tree[idx]) return -1;
        if (l==r) return l;
        int mid=(l+r)>>1;
        int res = -1;
        if (qr > mid)
            res = find_last(idx<<1|1, mid+1, r, max(ql,mid+1), qr);
        if (res != -1)
            return res;
        if (ql <= mid)
            res = find_last(idx<<1, l, mid, ql, min(qr,mid));
        return res;
    }
    int find_last(int ql, int qr) {
        return find_last(1,0,n-1, ql, qr);
    }
    // znajdź pierwsze delta!=0 w [ql..qr], lub n jeśli brak
    int find_first(int idx, int l, int r, int ql, int qr) {
        if (ql>qr || !tree[idx]) return -1;
        if (l==r) return l;
        int mid=(l+r)>>1;
        int res = -1;
        if (ql <= mid)
            res = find_first(idx<<1, l, mid, ql, min(qr,mid));
        if (res != -1)
            return res;
        if (qr > mid)
            res = find_first(idx<<1|1, mid+1, r, max(ql,mid+1), qr);
        return res;
    }
    int find_first(int ql, int qr) {
        return find_first(1,0,n-1, ql, qr);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<pair<int,int>> mast(N);
    int maxH = 0;
    for(int i=0;i<N;i++){
        cin >> mast[i].first >> mast[i].second;
        maxH = max(maxH, mast[i].first);
    }
    // sortujemy po rosnącej wysokości H
    sort(mast.begin(), mast.end());

    // przygotowujemy delta[0..maxH+1], indeksujemy 1-based
    int M = maxH + 2;
    vector<ll> delta(M, 0);
    SegTree st(M);

    // funkcja pomocnicza: zmień delta[pos] o val i zaktualizuj drzewo
    auto apply = [&](int pos, ll val){
        delta[pos] += val;
        st.update(pos, delta[pos] != 0);
    };

    // przetwarzamy kolejne maszty
    for(auto &p : mast){
        int H = p.first;
        int K = p.second;
        // dodajemy poziomy do max-widoczności (delta już ma rozmiar M)
        // teraz musimy dodać +1 na każdym poziomie z przedziału [A..H]
        int A = H - K + 1;
        if (A < 1) A = 1;

        // sprawdzamy, czy A leży wewnątrz grupy zer:
        bool inGroup = (delta[A] == 0);

        if (!inGroup) {
            // prosty przypadek: jedna operacja delta[A]++, delta[H+1]--
            apply(A, +1);
            apply(H+1, -1);
        } else {
            // musimy znaleźć granice grupy zer zawierającej A
            int left_nonzero  = st.find_last(0, A-1);
            int L = (left_nonzero == -1 ? 1 : left_nonzero+1);
            int right_nonzero = st.find_first(A+1, M-1);
            int R = (right_nonzero == -1 ? H : right_nonzero-1);

            // długość prawej części w grupie: segment [A..R]
            int lenRight = R - A + 1;
            // będziemy robić dwie aktualizacje:
            // 1) przedział [L .. L+lenRight-1]  +=1
            // 2) przedział [R+1 .. H]          +=1
            int mid1 = L + lenRight - 1;
            apply(L, +1);
            apply(mid1+1, -1);

            if (R+1 <= H) {
                apply(R+1, +1);
                apply(H+1, -1);
            }
        }
    }

    // na koniec budujemy histogram S[L] jako prefix-sum delta
    vector<ll> S(M,0);
    for(int i=1;i<=maxH;i++){
        S[i] = S[i-1] + delta[i];
    }

    // liczmy niesprawność: suma C(S[L],2)
    ll result = 0;
    for(int i=1;i<=maxH;i++){
        result += S[i] * (S[i]-1) / 2;
    }
    cout << result << "\n";
    return 0;
}

• Subtask 1: 0 / 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