Submission #1135195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135195		apark0731	정전 (OJUZ10_blackout)	C++20	0 / 100	5 ms	2632 KiB

blackout

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int n, l;
  cin >> n >> l;
  
  pair<int, int> a[300100];
  
  int k;
  
  for (int i = 0 ; i < n ; i++){
    cin >> k;
    if (i%2 == 0){  // a
      a[2*i] = {k-l, 1}; //on, k-l is starting point of light
      a[2*i+1] = {k+l, -1}; //off, k+l is end point of light
    }
    else{ //b
      a[2*i] = {k-l, 2}; //on
      a[2*i+1] = {k+l, -2}; //off
    }
  }
  
  sort(&a[0], &a[2*n]);
  
  for (int i = 0 ; i < 2*n ; i++){
    //cout << a[i].first << " " << a[i].second << endl;
  }
  
  int count = 0;
  bool aon = false, bon = false;
  int amax, bmax;
  int prev; //prev = where overlap starts?
  bool overlap = false;
  
  for (int i = 0 ; i < 2*n ; i++){ //abababab order, a is always before b
    if (a[i].second == 1){
      aon = true;
      amax = a[i].first+2*l;
      if (overlap == false){
        if (bon == true){ //if this caused the overlapping region to begin
          overlap = true;
          prev = a[i].first;
        }
      }
    }
    else if (a[i].second == -1){
      if (amax == a[i].first){ //this means that only this light of group a has been turned on right now
        aon = false;
        if (overlap == true){
          overlap = false;
          count+=a[i].first - prev;
        }
      }
    }
    else if (a[i].second == 2){
      bon = true;
      bmax = a[i].first+2*l;
      if (overlap == false){
        if (aon == true){
          overlap = true;
          prev = a[i].first;
        }
      }
    }
    else if (a[i].second == -2){
      if (bmax == a[i].first){
        bon = false;
        if (overlap == true){
          overlap = false;
          count+=a[i].first - prev;
        }
      }
    }
  }
  
  cout << count;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40