Submission #1028371

#TimeUsernameProblemLanguageResultExecution timeMemory
1028371a5a7Sails (IOI07_sails)C++14
70 / 100
555 ms6612 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 pushdown(int left, int mid, int right, int node){ if ((node*2+2) >= length){ arr[node].add = 0; return; } arr[node*2+1].add += arr[node].add; arr[node*2+1].value += ll(mid-left+1) * arr[node].add; arr[node*2+2].add += arr[node].add; arr[node*2+2].value += ll(right-mid) * arr[node].add; arr[node].add = 0; } void pushup(int node){ if ((node*2+2) >= length) return; arr[node].value = arr[node*2+2].value + arr[node*2+1].value; } 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].value += ad * ll(end-start+1); arr[node].add += ad; return; } int mid = (start+end)/2; pushdown(start, mid, end, node); add(left, right, start, mid, node*2+1, ad); add(left, right, mid+1, end, node*2+2, ad); pushup(node); } 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; int mid = (start+end)/2; pushdown(start, mid, end, node); 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); int last = 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 = n-1; 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(a[i].first-a[i].second, a[i].first-1, 0, arrl-1, 0, 1ll); add(a[i].first-a[i].second, end, 0, arrl-1, 0, -1ll); add(start, start + end-a[i].first+a[i].second, 0, arrl-1, 0, 1ll); } cout << ans << endl; }

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:72:9: warning: unused variable 'last' [-Wunused-variable]
   72 |     int last = 100000;
      |         ^~~~
#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...