Submission #1117269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117269		Trisanu_Das	Lasers (NOI19_lasers)	C++17	51 / 100	1074 ms	54028 KiB

lasers

#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 / 10
• Subtask 2: 0 / 14
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 0 / 22
• Subtask 6: 0 / 13