Submission #671904

#	Time	Username	Problem	Language	Result	Execution time	Memory
671904		omkarbajaj073	Lasers (NOI19_lasers)	C++17	51 / 100	1092 ms	52912 KiB

lasers

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