oj.uz

Submission #1090217

# Submission time Handle Problem Language Result Execution time Memory
1090217 2024-09-18T03:24:54 Z eysbutno Sails (IOI07_sails) C++17
100 / 100
 99 ms 2248 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

  public:
	BIT(int size) : size(size), bit(size + 1), arr(size) {}

	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;
	}
};

template <typename T, typename F> 
T first_true(T low, T high, const F &fn) {
    while (low < high) {
        T mid = low + (high - low) / 2;
        fn(mid) ? high = mid : low = mid + 1;
    }
    return low;
}

int main() {
    int n; cin >> n;
    vector<int> h(n), k(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i] >> k[i];
    }
    vector<int> ord(n);
    iota(begin(ord), end(ord), 0);
    sort(begin(ord), end(ord), [&](int i, int j) -> bool {
        return h[i] < h[j];
    });
    const int MX = *max_element(begin(h), end(h));
    BIT<int> bit(MX + 1);
    for (int i : ord) {
        int last = h[i] - k[i];
        int val = bit.pref_sum(last);
        int idx_1 = first_true(0, h[i], [&](int x) -> bool {
            return bit.pref_sum(x) < val;
        });
        int idx_2 = first_true(0, h[i], [&](int x) -> bool {
            return bit.pref_sum(x) <= val;
        });
        bit.add(idx_1, 1);
        bit.add(h[i], -1);
        bit.add(idx_2, 1);
        bit.add(idx_2 + k[i] - (h[i] - idx_1), -1);
    }   
    ll res = 0;
    for (int i = 0; i < MX; i++) {
        int cnt = bit.pref_sum(i);
        res += 1ll * cnt * (cnt - 1) / 2;
    }
    cout << res << "\n";
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 444 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 604 KB Output is correct
2 Correct 17 ms 604 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 780 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1368 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 1884 KB Output is correct
2 Correct 66 ms 2072 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2164 KB Output is correct
2 Correct 66 ms 2132 KB Output is correct

Subtask #11
10.0 / 10.0

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