Submission #1090217

#TimeUsernameProblemLanguageResultExecution timeMemory
1090217eysbutnoSails (IOI07_sails)C++17
100 / 100
99 ms2248 KiB
#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"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...