Submission #237779

#	Time	Username	Problem	Language	Result	Execution time	Memory
237779		Haunted_Cpp	Lasers (NOI19_lasers)	C++17	41 / 100	751 ms	262144 KiB

lasers

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

const int N = 1e6 + 5;

int dp [N];

const int MAX_N = 1000000000 + 5;
const int ROOT = 0;
const int NODE = 1e7 + 5;

int L [NODE], R [NODE], Time = 0;

int seg [NODE];
short lazy [NODE];
 
int expandir (int delta) {
  if (~delta) return delta;
  return ++Time;
}
 
void push (int l, int r, int where) {
  if (lazy[where] == 0) return;
  const int mid = l + (r - l) / 2;
  if (l != r) {
    L[where] = expandir (L[where]);
    R[where] = expandir (R[where]);
    
    seg[L[where]] += lazy[where] * (mid - l + 1);
    seg[R[where]] += lazy[where] * (r - (mid + 1) + 1);

    lazy[L[where]] += lazy[where];
    lazy[R[where]] += lazy[where];
  }
  lazy[where] = 0;
}

void modify (int l, int r, int where, int ql, int qr) {
  if (l > qr || r < ql) return;
  if (l >= ql && r <= qr) {
    seg[where] += (r - l + 1);
    ++lazy[where];
    return;
  }
  const int mid = l + (r - l) / 2;
  push (l, r, where);
  if (mid >= ql) {
    L[where] = expandir (L[where]);
    modify (l, mid, L[where], ql, qr);
  }
  if (mid + 1 <= qr) {
    R[where] = expandir (R[where]);
    modify (mid + 1, r, R[where], ql, qr);
  }
  seg[where] = (~L[where] ? seg[L[where]] : 0) + (~R[where] ? seg[R[where]] : 0);
}

int res = 0, goal;

void solve (int l, int r, int where) {
  if (where == -1) {
    res += (r - l + 1);
    return;
  }
  if (l == r) {
    res += (seg[where] != goal);
    return;
  }
  const int mid = l + (r - l) / 2;
  push (l, r, where);
  solve (l, mid, L[where]);
  solve (mid + 1, r, R[where]);
}
 
int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int l, r;
  cin >> l >> r;
  goal = r;
  for (int i = 0; i < NODE; i++) {
    L[i] = R[i] = -1;
    seg[i] = 0;
    lazy[i] = 0;
  }
  for (int T = 0; T < r; T++) {
    int qts;
    cin >> qts;
    int s = 0;
    vector<int> arr (qts);
    for (int i = 0; i < qts; i++) {
      cin >> arr[i];
      s += arr[i];
    }
    int cur = 0;
    int mn = 0;
    int st, et;
    for (int i = 0; i < qts; i++) {
      st = max (mn, cur);
      et = l - s - 1;
      modify (0, l - 1, ROOT, st, et);
      mn = max (mn, l - s);
      cur += arr[i];
      s -= arr[i];
    } 
    st = max (mn, cur);
    et = l - s - 1;
    modify (0, l - 1, ROOT, st, et);
  };
  solve (0, l - 1, ROOT);
  cout << res << '\n';
  return 0;
}

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