제출 #1158759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158759		aeg	Lasers (NOI19_lasers)	C++20	100 / 100	68 ms	7360 KiB

lasers

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

struct segmentset {
  set<pair<int, int>> s;
  int ans() {
    int ret = 0;
    for(auto &[x, y]: s) ret += y - x + 1;
    return ret;
  }
  void insert(int l, int r) {
    auto a = s.lower_bound({
	l, INT_MIN});
    while (a != s.end() && r >= a->first - 1) {
      r = max(r, a->second);
      l = min(l, a->first);
      s.erase(*a);
      a = s.lower_bound({
	  l, INT_MIN});
    }
    while (a != s.begin()) {
      a--;
      if (l <= a->second + 1) {
	l = min(l, a->first);
	r = max(r, a->second);
	s.erase(*a);
	a = s.lower_bound({
	    l, INT_MIN});
      }
      else break;
    }
    s.insert({l, r});
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int l, r;
  cin >> l >> r;
  segmentset s;
  while (r--) {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> ri(n);
    vector<int> li(n);
    for (auto &x : a) {
      cin >> x;
    }
    int curi = 0;
    for (int i = 0; i < n; i++) {
      curi += a[i];
      ri[i] = curi;
    }
    curi = l + 1;
    for (int i = n-1; i >= 0; i--) {
      curi -= a[i];
      li[i] = curi;
    }
    for (int i = 0; i < n; i++) {
      if(li[i] <= ri[i]) s.insert(li[i], ri[i]);
    }
  }
  cout << s.ans() << '\n';
}

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