oj.uz

Submission #237780

# Submission time Handle Problem Language Result Execution time Memory
237780 2020-06-08T18:10:33 Z Haunted_Cpp Lasers (NOI19_lasers) C++17
41 / 100
 868 ms 262144 KB 
#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 = 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;

  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

# Verdict Execution time Memory Grader output
1 Runtime error 306 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

# Verdict Execution time Memory Grader output
1 Runtime error 306 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

# Verdict Execution time Memory Grader output
1 Correct 169 ms 137976 KB Output is correct
2 Correct 116 ms 137592 KB Output is correct
3 Correct 119 ms 137516 KB Output is correct
4 Correct 173 ms 137856 KB Output is correct
5 Correct 136 ms 137848 KB Output is correct
6 Correct 201 ms 138744 KB Output is correct
7 Correct 94 ms 137336 KB Output is correct
8 Correct 226 ms 138472 KB Output is correct
9 Correct 136 ms 137720 KB Output is correct
10 Correct 185 ms 138036 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 137336 KB Output is correct
2 Correct 90 ms 137336 KB Output is correct
3 Correct 79 ms 137336 KB Output is correct
4 Correct 78 ms 137336 KB Output is correct
5 Correct 79 ms 137336 KB Output is correct
6 Correct 91 ms 137336 KB Output is correct
7 Correct 81 ms 137336 KB Output is correct
8 Correct 94 ms 137336 KB Output is correct
9 Correct 79 ms 137336 KB Output is correct
10 Correct 91 ms 137336 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 137976 KB Output is correct
2 Correct 116 ms 137592 KB Output is correct
3 Correct 119 ms 137516 KB Output is correct
4 Correct 173 ms 137856 KB Output is correct
5 Correct 136 ms 137848 KB Output is correct
6 Correct 201 ms 138744 KB Output is correct
7 Correct 94 ms 137336 KB Output is correct
8 Correct 226 ms 138472 KB Output is correct
9 Correct 136 ms 137720 KB Output is correct
10 Correct 185 ms 138036 KB Output is correct
11 Correct 91 ms 137336 KB Output is correct
12 Correct 90 ms 137336 KB Output is correct
13 Correct 79 ms 137336 KB Output is correct
14 Correct 78 ms 137336 KB Output is correct
15 Correct 79 ms 137336 KB Output is correct
16 Correct 91 ms 137336 KB Output is correct
17 Correct 81 ms 137336 KB Output is correct
18 Correct 94 ms 137336 KB Output is correct
19 Correct 79 ms 137336 KB Output is correct
20 Correct 91 ms 137336 KB Output is correct
21 Incorrect 868 ms 137336 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 306 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -