Submission #1314673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314673		joshjuice	Lasers (NOI19_lasers)	C++20	100 / 100	89 ms	8588 KiB

lasers

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef deque<int> dqi;
typedef pair<ll, ll> pll;

#define ppf pop_front
#define pf push_front
#define pb push_back
#define fr first
#define sc second
#define all(a) a.begin(), a.end()
#define sr(a) sort(all(a))
#define sz(a) a.size()
#define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--))
#define mnto(x,y) x = min(x, (__typeof__(x))y)
#define mxto(x,y) x = max(x, (__typeof__(x))y)

const ll INF1 = 1e18;
const ll INF2 = 1e15;
const ll INF3 = 1e14;

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  ll l;
  int r, x;
  cin >> l >> r;
  vector<pll> avail;
  rep(i, 0, r) {
    cin >> x;
    vll a(x);
    rep(i, 0, x) cin >> a[i];
    vll ps(x+1, 0);
    rep(i, 0, x) ps[i+1] = ps[i]+a[i];
    ll total = ps[x];
    ll d = l-total; //remaining guranteed spaces
    rep(j, 0, x) {
      ll leftl = ps[j]+1;
      ll leftr = ps[j]+a[j];
      ll rightl = leftl+d;
      ll rightr = leftr+d;
      ll gl = max(leftl, rightl);
      ll gr = min(leftr, rightr);
      if (gl <= gr) {
        avail.emplace_back(gl, gr); 
      }
    }
  }
  sr(avail);
  vector<pll> merged;
  for (auto [l, r] : avail) {
    if (!sz(merged) || l > merged.back().sc+1) merged.emplace_back(l, r);
    else mxto(merged.back().sc, r);
  }
  ll ans = 0;
  for (auto [l, r] : merged) ans += r-l+1;
  cout << ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 22 / 22
• Subtask 6: 13 / 13