Submission #1016382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016382		Zero_OP	Sails (IOI07_sails)	C++14	100 / 100	39 ms	2652 KiB

sails

#include<bits/stdc++.h>

using namespace std;

template<typename T> bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

template<typename T> bool maximize(T& a, const T& b){
    if(a < b) return a = b, true;
    return false;
}

struct mast{
    int h, k;
    mast(int h = 0, int k = 0) : h(h), k(k) {}
    bool operator < (const mast& o) const{
        return h < o.h || (h == o.h && k < o.k);
    }

    friend istream& operator >> (istream& in, mast& p){
        return in >> p.h >> p.k;
    }
};

const int MAX = 1e5 + 1;

struct Fenwick{
    vector<int> bit;
    Fenwick(int n) : bit(n + 1) {}

    void update(int id, int val){
        for(; id < (int)bit.size(); id += id & (-id)){
            bit[id] += val;
        }
    }

    int query(int id){
        int sum = 0;
        for(; id > 0; id -= id & (-id)){
            sum += bit[id];
        }
        return sum;
    }

    int walk(int x){
        int pos = 0;
        for(int step = (1 << 16); step > 0; step >>= 1){
            if(pos + step < (int)bit.size() && bit[pos + step] >= x){
                pos += step;
                x -= bit[pos];
            }
        }
        return pos;
    }

    int f(int x){
        int l = 0, r = (int)bit.size() - 1, ans = 0;
        while(l <= r){
            int mid = l + r >> 1;
            if(query(mid) >= x) ans = mid, l = mid + 1;
            else r = mid - 1;
        }
        return ans;
    }
};

int n;
mast masts[MAX];

void testcase(){
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> masts[i];
    }

    int lim = 1e5;
    Fenwick T(lim);
    sort(masts, masts + n);
    for(int i = 0; i < n; ++i){
        int h = masts[i].h, k = masts[i].k;
        int l = h - k + 1;
        if(h == k){
            T.update(l, +1);
            T.update(h + 1, -1);
        }
        else{
            int target_cur = T.query(l);
            int target_pre = T.query(l - 1);
            if(target_cur != target_pre){
                T.update(l, +1);
                T.update(h + 1, -1);
                continue;
            }

            int id = T.walk(target_cur);
            if(target_cur){
                T.update(id + 1, +1);
                T.update(h + 1, -1);
                k -= (h - id);
            }

            id = T.walk(T.query(l) + 1);
            T.update(id + 1, +1);
            T.update(id + 1 + k, -1);
        }

    }

    long long inefficiency = 0;
    for(int i = 1; i <= lim; ++i){
        int cnt = T.query(i);
        inefficiency += 1LL * cnt * (cnt - 1) / 2;
    }
    cout << inefficiency << '\n';
}

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

    int t = 1;
    //cin >> t;

    while(t--){
        testcase();
    }

    return 0;
}

Compilation message (stderr)

sails.cpp: In member function 'int Fenwick::f(int)':
sails.cpp:61:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |             int mid = l + r >> 1;
      |                       ~~^~~

• 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