oj.uz

Submission #671904

# Submission time Handle Problem Language Result Execution time Memory
671904 2022-12-14T08:36:46 Z omkarbajaj073 Lasers (NOI19_lasers) C++17
51 / 100
 1000 ms 52912 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_X = 500010;

map<int, int> cnt;
int tot = 0, pref[MAX_X];

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

    // if (pref[k] <= N/2) continue;

    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());

  // cout << "Points: " << endl;
  // for (auto point : points) { cout << point << endl; }
  // cout << "Events: " << endl;
  // for (auto event : events) { cout << event.first << " " << event.second << endl; }
  
  int ans = N;

  int ind = 0;
  int esz = events.size();
  int psz = points.size();

  // int prev = 0;
  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 << endl;

  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 673 ms 52156 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Execution timed out 1069 ms 52912 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 11992 KB Output is correct
2 Correct 18 ms 3468 KB Output is correct
3 Correct 26 ms 3520 KB Output is correct
4 Correct 94 ms 12116 KB Output is correct
5 Correct 61 ms 6504 KB Output is correct
6 Correct 114 ms 12960 KB Output is correct
7 Correct 2 ms 656 KB Output is correct
8 Correct 154 ms 13460 KB Output is correct
9 Correct 41 ms 6440 KB Output is correct
10 Correct 116 ms 12232 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 11992 KB Output is correct
2 Correct 18 ms 3468 KB Output is correct
3 Correct 26 ms 3520 KB Output is correct
4 Correct 94 ms 12116 KB Output is correct
5 Correct 61 ms 6504 KB Output is correct
6 Correct 114 ms 12960 KB Output is correct
7 Correct 2 ms 656 KB Output is correct
8 Correct 154 ms 13460 KB Output is correct
9 Correct 41 ms 6440 KB Output is correct
10 Correct 116 ms 12232 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Execution timed out 1092 ms 51196 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 673 ms 52156 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Execution timed out 1069 ms 52912 KB Time limit exceeded
18 Halted 0 ms 0 KB -