oj.uz

Submission #1016382

# Submission time Handle Problem Language Result Execution time Memory
1016382 2024-07-08T02:46:05 Z Zero_OP Sails (IOI07_sails) C++14
100 / 100
 39 ms 2652 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1628 KB Output is correct
2 Correct 2 ms 1628 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1628 KB Output is correct
2 Correct 2 ms 1628 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 2 ms 1624 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1628 KB Output is correct
2 Correct 2 ms 1628 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1512 KB Output is correct
2 Correct 2 ms 1628 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1580 KB Output is correct
2 Correct 11 ms 1868 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1884 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2140 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2392 KB Output is correct
2 Correct 28 ms 2396 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2532 KB Output is correct
2 Correct 23 ms 2140 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2652 KB Output is correct
2 Correct 25 ms 2648 KB Output is correct