Submission #1007937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007937		devariaota	Lasers (NOI19_lasers)	C++17	100 / 100	79 ms	9136 KiB

lasers

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;
const int maxq = 5e5;

int n, q;
int k, b[maxq+5];
vector<pair<int, int>> v; // list of segments that are defended no matter what

// given a base of length n (1...n)
// a laser will be shot from afar
// there are q layers of defense
// each layer of defense consist of k walls of length b[j] for 1 <= j <= k
// those walls must be placed in order of the input (i.e. the j-th wall must be placed before the j+1th wall)
// walls can not overlap

signed main() {
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin >> n >> q;
  for (int i=1; i<=q; i++) {
    cin >> k;
    int suff = 0, pref = 0;
    for (int j=1; j<=k; j++) {
      cin >> b[j];
      suff += b[j];
    }
    for (int j=1; j<=k; j++) {
      int l = pref+1, r = n - suff + b[j];
      int lb = r - b[j] + 1, rb = l + b[j] - 1;
      if (lb <= rb) v.push_back({lb, rb});
      pref += b[j];
      suff -= b[j];
    }
  }
  sort(v.begin(), v.end());
  int lb = 0, rb = -1, ans = 0;
  for (auto i: v) {
    if (rb < i.fi) {
      ans += rb - lb + 1;
      lb = i.fi;
      rb = i.se;
      continue;
    }
    rb = max(rb, i.se);
  }
  ans += rb - lb + 1;
  cout << ans << endl;
  return 0;
}

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