Submission #1222543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222543		bbldrizzy	Sails (IOI07_sails)	C++20	100 / 100	54 ms	1976 KiB

sails

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;

template <class T> class BIT {
  private:
	int size;
    int LOGN = 0;
	vector<T> bit;
	vector<T> arr;

  public:
	BIT(int size) : size(size), bit(size + 1), arr(size) {
        LOGN = 0;
        while ((1 << (LOGN+1)) <= size) {
            LOGN++;
        }
    }

	void set(int ind, T val) { add(ind, val - arr[ind]); }

	void add(int ind, T val) {
		arr[ind] += val;
		ind++;
		for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
	}

	T pref_sum(int ind) {
		ind++;
		T total = 0;
		for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
		return total;
	}

    int first_below(int v) {
        int sum = 0, pos = 0;
        for (int k = LOGN; k >= 0; --k) {
            int nxt = pos + (1 << k);
            if (nxt <= size && sum + bit[nxt] >= v) {
                sum += bit[nxt];
                pos = nxt;
            }
        }
        return pos;
    }
};

int main() {
    int n; cin >> n;
    vector<pair<int, int>> poles;
    int mx = 0;
    for (int i = 0; i < n; i++) {
        int a, b; cin >> a >> b;
        mx = max(mx, a);
        poles.push_back({a, b});
    }
    sort(poles.begin(), poles.end());
    BIT<int> bit(mx+1);
    for (int i = 0; i < n; i++) {
        int h = poles[i].f;
        int k = poles[i].s;
        int v = bit.pref_sum(h-k);
        int idx1 = min(h, bit.first_below(v));
        int idx2 = min(h, bit.first_below(v+1));
        bit.add(idx1, 1);
        bit.add(h, -1);
        bit.add(idx2, 1);
        bit.add(idx2 + k - (h - idx1), -1);
    }
    ll ans = 0;
    for (int i = 0; i < mx; i++) {
        ll x = bit.pref_sum(i);
        ans += (x*(x-1))/2;
    }
    cout << ans;
}

• 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