fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<int, int>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. struct Line
  12. {
  13.     int l, r;
  14.  
  15.     Line(int l = 0, int r = 0) :
  16.         l(l), r(r) {};
  17.     Line operator & (Line other)
  18.     {
  19.         Line ans;
  20.         ans.l = max(l, other.l);
  21.         ans.r = min(r, other.r);
  22.         return ans;
  23.     }
  24. };
  25.  
  26. const int maxn = 5e5;
  27.  
  28. int L, R, a[maxn + 10], ans = 0, cnt = 0;
  29. vector<ii> points;
  30.  
  31. int main()
  32. {
  33.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  34.     if (fopen("LASER.INP", "r"))
  35.     {
  36.         freopen("LASER.INP", "r", stdin);
  37.         freopen("LASER.OUT", "w", stdout);
  38.     }
  39.  
  40.     cin >> L >> R;
  41.     for (int i = 1; i <= R; i++)
  42.     {
  43.         int n, pre = 0, suf = 0;
  44.         cin >> n;
  45.         for (int i = 1; i <= n; i++)
  46.         {
  47.             cin >> a[i];
  48.             suf += a[i];
  49.         }
  50.         for (int i = 1; i <= n; pre += a[i], i++)
  51.         {
  52.             suf -= a[i];
  53.             int l_1 = pre + 1;
  54.             int r_1 = l_1 + a[i] - 1;
  55.             int r_2 = L - suf;
  56.             int l_2 = r_2 - a[i] + 1;
  57.             Line intersect = Line(l_1, r_1) & Line(l_2, r_2);
  58.             if (intersect.l > intersect.r)
  59.                 continue;
  60.             points.push_back(ii(intersect.l, 1));
  61.             points.push_back(ii(intersect.r + 1, -1));
  62.         }
  63.     }
  64.     sort(points.begin(), points.end());
  65. //    for (ii pr : points)
  66. //        cout << pr.fi << ' ' << pr.se, el;
  67.     for (int i = 0; i < points.size(); )
  68.     {
  69.         if (cnt)
  70.             ans += points[i].fi - points[i - 1].fi;
  71.         int j = i;
  72.         while (j < points.size() && points[i].fi == points[j].fi)
  73.         {
  74.             cnt += points[j].se;
  75.             j++;
  76.         }
  77. //        cout << i << ' ' << j << ' ' << delta, el;
  78.         i = j;
  79.     }
  80.     cout << ans;
  81. }
  82.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/v9ZNrK
language:
C++14 (gcc 8.3)
created:
20 hours 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!