This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int MAX_N = 1000000000 + 5;
const int ROOT = 0;
const int NODE = 5e6 + 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;
if (l != r) {
L[where] = expandir (L[where]);
R[where] = expandir (R[where]);
seg[L[where]] += lazy[where];
seg[R[where]] += lazy[where];
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];
++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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |