oj.uz

답안 #237782

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237782 2020-06-08T18:12:13 Z Haunted_Cpp Lasers (NOI19_lasers) C++17
41 / 100
 885 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

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

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

short 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;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 645 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 645 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 234 ms 235784 KB Output is correct
2 Correct 194 ms 235384 KB Output is correct
3 Correct 189 ms 235384 KB Output is correct
4 Correct 232 ms 235904 KB Output is correct
5 Correct 213 ms 235768 KB Output is correct
6 Correct 269 ms 236536 KB Output is correct
7 Correct 151 ms 235256 KB Output is correct
8 Correct 302 ms 236248 KB Output is correct
9 Correct 195 ms 235516 KB Output is correct
10 Correct 233 ms 235956 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 235232 KB Output is correct
2 Correct 142 ms 235128 KB Output is correct
3 Correct 140 ms 235256 KB Output is correct
4 Correct 163 ms 235128 KB Output is correct
5 Correct 173 ms 235128 KB Output is correct
6 Correct 140 ms 235000 KB Output is correct
7 Correct 149 ms 235312 KB Output is correct
8 Correct 139 ms 235128 KB Output is correct
9 Correct 161 ms 235128 KB Output is correct
10 Correct 162 ms 235128 KB Output is correct

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 234 ms 235784 KB Output is correct
2 Correct 194 ms 235384 KB Output is correct
3 Correct 189 ms 235384 KB Output is correct
4 Correct 232 ms 235904 KB Output is correct
5 Correct 213 ms 235768 KB Output is correct
6 Correct 269 ms 236536 KB Output is correct
7 Correct 151 ms 235256 KB Output is correct
8 Correct 302 ms 236248 KB Output is correct
9 Correct 195 ms 235516 KB Output is correct
10 Correct 233 ms 235956 KB Output is correct
11 Correct 166 ms 235232 KB Output is correct
12 Correct 142 ms 235128 KB Output is correct
13 Correct 140 ms 235256 KB Output is correct
14 Correct 163 ms 235128 KB Output is correct
15 Correct 173 ms 235128 KB Output is correct
16 Correct 140 ms 235000 KB Output is correct
17 Correct 149 ms 235312 KB Output is correct
18 Correct 139 ms 235128 KB Output is correct
19 Correct 161 ms 235128 KB Output is correct
20 Correct 162 ms 235128 KB Output is correct
21 Incorrect 885 ms 235292 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 645 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -