fork download
copy 
  1. #pragma GCC optimize("Ofast,unroll-loops")
  2. #pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  7. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  8. #define nl "\n"
  9. #define ss " "
  10. #define pb emplace_back
  11. typedef long long ll;
  12.  
  13. const int maxn = 500000 + 15;
  14.  
  15. int n;
  16. int a[maxn], b[maxn];
  17. ll l[maxn], r[maxn];
  18. stack<int> st;
  19.  
  20. inline void enlarge(int i, int j) {
  21.     l[i] = min(l[i], l[j]);
  22.     r[i] = max(r[i], r[j]);
  23.     a[i] = min(a[i], a[j]);
  24.     b[i] = max(b[i], b[j]);
  25. }
  26.  
  27. void solve() {
  28.     // forward pass
  29.     while(!st.empty()) st.pop();
  30.     ff(i, 1, n) {
  31.         while(!st.empty() && l[i] <= r[st.top()]) {
  32.             int u = st.top(); st.pop();
  33.             enlarge(i, u);
  34.             a[u] = a[i]; b[u] = b[i]; // propagate cho phần tử pop
  35.         }
  36.         st.push(i);
  37.     }
  38.     // backward pass
  39.     while(!st.empty()) st.pop();
  40.     ffr(i, n, 1) {
  41.         while(!st.empty() && r[i] >= l[st.top()]) {
  42.             int u = st.top(); st.pop();
  43.             enlarge(i, u);
  44.             a[u] = a[i]; b[u] = b[i]; // propagate cho phần tử pop
  45.         }
  46.         st.push(i);
  47.     }
  48. }
  49.  
  50. int main() {
  51.     ios::sync_with_stdio(false);
  52.     cin.tie(nullptr);
  53.  
  54.     cin >> n;
  55.     ff(i, 1, n) {
  56.         ll x, rad;
  57.         cin >> x >> rad;
  58.         l[i] = x - rad;
  59.         r[i] = x + rad;
  60.         a[i] = b[i] = i; // khởi tạo
  61.     }
  62.  
  63.     solve();
  64.  
  65.     ll ans = 0;
  66.     ff(i, 1, n) {
  67.         ll si = b[i] - a[i] + 1;
  68.         ans += 1ll * i * si;
  69.         // cout << i << ss << si << nl; // chỉ để debug nếu muốn
  70.     }
  71.     cout << ans << nl;
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0.01s 9772KB
comments (?)
stdin
copy 
4
1 1
5 1
6 5
15 15
stdout
copy 
40
https://ideone.com/zB1BCE
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!