fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const int INF = 1e9;
  5.  
  6. struct SegMin {
  7.     int n; vector<int> st;
  8.     SegMin(){}
  9.     SegMin(const vector<int>& a){ build(a); }
  10.     void build(const vector<int>& a){
  11.         int m = a.size()-1;
  12.         n = 1; while(n < m) n <<= 1;
  13.         st.assign(2*n, INF);
  14.         for(int i=1;i<=m;i++) st[n+i-1] = a[i];
  15.         for(int i=n-1;i>=1;i--) st[i]=min(st[2*i], st[2*i+1]);
  16.     }
  17.     int query(int l,int r){
  18.         if(l>r) return INF;
  19.         l = l + n - 1; r = r + n - 1;
  20.         int res = INF;
  21.         while(l<=r){
  22.             if(l&1) res = min(res, st[l++]);
  23.             if(!(r&1)) res = min(res, st[r--]);
  24.             l >>= 1; r >>= 1;
  25.         }
  26.         return res;
  27.     }
  28. };
  29.  
  30. struct SegMax {
  31.     int n; vector<int> st;
  32.     SegMax(){}
  33.     SegMax(const vector<int>& a){ build(a); }
  34.     void build(const vector<int>& a){
  35.         int m = a.size()-1;
  36.         n = 1; while(n < m) n <<= 1;
  37.         st.assign(2*n, 0);
  38.         for(int i=1;i<=m;i++) st[n+i-1] = a[i];
  39.         for(int i=n-1;i>=1;i--) st[i]=max(st[2*i], st[2*i+1]);
  40.     }
  41.     int query(int l,int r){
  42.         if(l>r) return 0;
  43.         l = l + n - 1; r = r + n - 1;
  44.         int res = 0;
  45.         while(l<=r){
  46.             if(l&1) res = max(res, st[l++]);
  47.             if(!(r&1)) res = max(res, st[r--]);
  48.             l >>= 1; r >>= 1;
  49.         }
  50.         return res;
  51.     }
  52. };
  53.  
  54. int main(){
  55.     ios::sync_with_stdio(false);
  56.     cin.tie(nullptr);
  57.     int n;
  58.     if(!(cin >> n)) return 0;
  59.     vector<long long> x(n+1), r(n+1);
  60.     for(int i=1;i<=n;i++) cin >> x[i] >> r[i];
  61.  
  62.     // direct intervals
  63.     vector<int> L0(n+1), R0(n+1);
  64.     for(int i=1;i<=n;i++){
  65.         long long leftpos = x[i] - r[i];
  66.         long long rightpos = x[i] + r[i];
  67.         int l = lower_bound(x.begin()+1, x.begin()+n+1, leftpos) - (x.begin()+1) + 1;
  68.         if(l < 1) l = 1;
  69.         int ridx = upper_bound(x.begin()+1, x.begin()+n+1, rightpos) - (x.begin()+1);
  70.         if(ridx < 1) ridx = 1;
  71.         if(ridx > n) ridx = n;
  72.         L0[i] = l;
  73.         R0[i] = ridx;
  74.     }
  75.  
  76.     // binary lifting levels
  77.     int LOG = 1;
  78.     while((1<<LOG) <= n) ++LOG;
  79.  
  80.     // left[k][i], right[k][i] after applying 2^k expansions starting from i (i interpreted as index interval [i,i])
  81.     // We'll store as vectors per level with 1-based indexing.
  82.     vector<vector<int>> leftk(LOG, vector<int>(n+1));
  83.     vector<vector<int>> rightk(LOG, vector<int>(n+1));
  84.  
  85.     // level 0 = direct
  86.     for(int i=1;i<=n;i++){ leftk[0][i] = L0[i]; rightk[0][i] = R0[i]; }
  87.  
  88.     // Build for levels k>=1
  89.     for(int k=1;k<LOG;k++){
  90.         // We need to compute for every i:
  91.         // leftk[k][i] = min_{j in [ leftk[k-1][i] .. rightk[k-1][i] ]} leftk[k-1][j]
  92.         // rightk[k][i] = max_{j in [ leftk[k-1][i] .. rightk[k-1][i] ]} rightk[k-1][j]
  93.         SegMin segmin(leftk[k-1]);
  94.         SegMax segmax(rightk[k-1]);
  95.         for(int i=1;i<=n;i++){
  96.             int l = leftk[k-1][i], r_ = rightk[k-1][i];
  97.             int nl = segmin.query(l, r_);
  98.             int nr = segmax.query(l, r_);
  99.             leftk[k][i] = nl;
  100.             rightk[k][i] = nr;
  101.         }
  102.     }
  103.  
  104.     // For each i compute final closure interval by greedy binary lifting:
  105.     ll ans = 0;
  106.     for(int i=1;i<=n;i++){
  107.         int L = leftk[0][i], R = rightk[0][i]; // start from direct (one step), could also start [i,i]
  108.         // try apply larger jumps from high to low: if applying expands, take it
  109.         for(int k = LOG-1; k>=0; --k){
  110.             // compute what applying 2^k on the whole current [L..R] would produce:
  111.             // that is: nl = min leftk[k][j] for j in [L..R], nr = max rightk[k][j] for j in [L..R]
  112.             // To answer these fast we can query precomputed segment trees per level.
  113.             // But we don't want to rebuild segtrees for every i; instead build segtrees per level once:
  114.             // To avoid rebuilding here, we create segtrees outside loop. (Do it above.)
  115.         }
  116.     }
  117.  
  118.     // The code above planned segtrees per level in the inner loop but we didn't build them outside.
  119.     // Let's build segtrees per level now and then re-run the final computation.
  120.  
  121.     vector<SegMin> segmins(LOG);
  122.     vector<SegMax> segmaxs(LOG);
  123.     for(int k=0;k<LOG;k++){
  124.         segmins[k].build(leftk[k]);
  125.         segmaxs[k].build(rightk[k]);
  126.     }
  127.  
  128.     // Now compute closures with those segtrees
  129.     ans = 0;
  130.     for(int i=1;i<=n;i++){
  131.         int L = leftk[0][i], R = rightk[0][i];
  132.         // We'll try to apply jumps to expand until fixed point
  133.         for(int k = LOG-1; k>=0; --k){
  134.             int nl = segmins[k].query(L, R);
  135.             int nr = segmaxs[k].query(L, R);
  136.             if(nl < L || nr > R){
  137.                 L = nl; R = nr;
  138.             }
  139.         }
  140.         ll si = (ll)R - (ll)L + 1;
  141.         ans += (ll)i * si;
  142.     }
  143.  
  144.     cout << ans << '\n';
  145.     return 0;
  146. }
  147.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
3
1 1
3 3
10 10
stdout
copy 
14
https://ideone.com/GzvoWg
language:
C++14 (gcc 8.3)
created:
8 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!