oj.uz

Submission #1117269

# Submission time Handle Problem Language Result Execution time Memory
1117269 2024-11-23T07:28:34 Z Trisanu_Das Lasers (NOI19_lasers) C++17
51 / 100
 1000 ms 54028 KB 
#include <bits/stdc++.h>
using namespace std;
 
map<int, int> cnt;
int tot = 0, pref[500010];
 
void ins (int a) {
  if (cnt[a]) cnt[a]++;
  else {
    cnt[a] = 1; tot++;
  }
};
 
void er (int a) {
  cnt[a]--;
  if (cnt[a] == 0) tot--;
};
 
 
int main() {
  
  ios_base::sync_with_stdio(false); cin.tie(0);
  int N, M; cin >> N >> M;
  vector<int> points;
  vector<pair<int, int>> events;
  for (int i = 1; i <= M; i++) {
    int k; cin >> k;
    for (int j = 0; j < k; j++) {
      int x; cin >> x;
      pref[j+1] = pref[j] + x; 
    }
    for (int j = 0; j <= k; j++) {
      points.push_back(pref[j] + 1); points.push_back(N - pref[k] + pref[j] + 1);
      events.push_back({pref[j] + 1, i}); events.push_back({N - pref[k] + pref[j] + 1, -i});
    }
  }
  sort(points.begin(), points.end());
  sort(events.begin(), events.end());
  points.erase(unique(points.begin(), points.end()), points.end());
  int ans = N, ind = 0, esz = events.size(), psz = points.size();
  for (int i = 0; i < psz; i++) {
    int point = points[i];
    while (ind < esz && events[ind].first == point) {
      if (events[ind].second > 0) ins(events[ind].second);
      else er(abs(events[ind].second));
      ind++;
    }
    if (tot == M) {
      if (i+1 < psz) ans -= points[i+1] - point;
      else ans -= N - point;
    }
  }
  cout << ans << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 602 ms 53736 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Execution timed out 1058 ms 54028 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 12212 KB Output is correct
2 Correct 16 ms 4540 KB Output is correct
3 Correct 24 ms 4540 KB Output is correct
4 Correct 88 ms 12204 KB Output is correct
5 Correct 68 ms 9652 KB Output is correct
6 Correct 123 ms 13984 KB Output is correct
7 Correct 2 ms 812 KB Output is correct
8 Correct 142 ms 14460 KB Output is correct
9 Correct 42 ms 9652 KB Output is correct
10 Correct 112 ms 12220 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 476 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 12212 KB Output is correct
2 Correct 16 ms 4540 KB Output is correct
3 Correct 24 ms 4540 KB Output is correct
4 Correct 88 ms 12204 KB Output is correct
5 Correct 68 ms 9652 KB Output is correct
6 Correct 123 ms 13984 KB Output is correct
7 Correct 2 ms 812 KB Output is correct
8 Correct 142 ms 14460 KB Output is correct
9 Correct 42 ms 9652 KB Output is correct
10 Correct 112 ms 12220 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 476 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 2 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Execution timed out 1074 ms 51768 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 602 ms 53736 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Execution timed out 1058 ms 54028 KB Time limit exceeded
18 Halted 0 ms 0 KB -