Submission #1028387

#TimeUsernameProblemLanguageResultExecution timeMemory
1028387a5a7Sails (IOI07_sails)C++14
100 / 100
415 ms6604 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using indexedset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; struct Node{ ll value = 0; ll add = 0; Node() {}; }; vector<Node> arr; int length, arrl; void build(int n){ arr.clear(); int powerOf2 = 1; while (powerOf2 < n) powerOf2 *= 2; n = powerOf2; length = 2 * n - 1, arrl = n; for (int i = 0; i < length; i++) arr.push_back(Node()); } void setval(int i, ll val){ int child = length-arrl+i; arr[child].value = val; while (child != 0){ if (child%2 == 0) child--; arr[(child-1)/2].value = arr[child].value + arr[child+1].value; child = (child-1)/2; } } void add(int left, int right, int start, int end, int node, ll ad){ if (left > end || right < start) return; if (left <= start && end <= right){ arr[node].add += ad; return; } int mid = (start+end)/2; arr[node].value += ll(min(end, right) - max(start, left) + 1) * ad; add(left, right, start, mid, node*2+1, ad); add(left, right, mid+1, end, node*2+2, ad); } ll range(int left, int right, int start, int end, int node){ if (left > end || right < start) return 0; if (left <= start && end <= right) return arr[node].value + arr[node].add * ll(end-start+1); int mid = (start+end)/2; arr[node].value += arr[node].add * ll(end-start+1); if ((node*2+2) < length){ arr[node*2+1].add += arr[node].add; arr[node*2+2].add += arr[node].add; } arr[node].add = 0; return range(left, right, start, mid, node*2+1) + range(left, right, mid+1, end, node*2+2); } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; build(100000); pair<int, int> a[n]; for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second; sort(a, a+n); ll ans = 0; function<int(int)> early = [&](int x){ int left = -1, right = 1e5; while (left < right){ int mid = (left+right+1)/2; if (range(mid, mid, 0, arrl-1, 0) >= x){ left = mid; }else{ right = mid-1; } } return left; }; for (int i = 0; i < n; i++){ ans += range(a[i].first-a[i].second, a[i].first-1, 0, arrl-1, 0); int val = range(a[i].first-a[i].second, a[i].first-a[i].second, 0, arrl-1, 0); int start = early(val+1)+1; int end = min(early(val), a[i].first-1); add(end+1, a[i].first-1, 0, arrl-1, 0, 1ll); add(start, start + end-a[i].first+a[i].second, 0, arrl-1, 0, 1ll); } cout << ans << endl; }
#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...