Southern Russia Open Championship 2019 G Girland

#include <cstdio>
#include <vector>

using namespace std;

struct Queue {
  int period;
  vector<int> deltas;
  vector<int> array;
  int takenSum;

  Queue(vector<int> array) {
    this->array = array;
  }

  void init(int start, int period) {
    period *= 2;
    this->position = start;
    this->moddedPosition = 0;
    this->period = period;
    deltas.assign(period, 0);
    for (int i = 0; i < period; i++) deltas[i] = 0;
    this->takenSum = 0;
    for (int i = start, j = 0; i < (int)array.size(); i++, j++) {
      if (i >= 0) {
        deltas[j % period] += array[i];
        if (j % period < period / 2) {
          takenSum += array[i];
        }
      }
    }
  }

  int position;
  int moddedPosition;
  void move() {
    takenSum -= deltas[moddedPosition];
    takenSum += deltas[(moddedPosition + period / 2) % period];
    if (position >= 0) deltas[moddedPosition] -= array[position];
    moddedPosition = (moddedPosition + 1) % period;
    position++;
  }
};

int main(int argc, char *argv[]) {
  int n, q;
  scanf("%d%d", &n, &q);
  vector<int> a(n);
  for (int i = 0; i < q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    for (int j = l; j < r; j++) a[j] = 1;
  }
  int ansMinAtHome = n + 1;
  int ansStart = -1;
  int ansLen = -1;
  Queue q1(a);
  Queue q2(vector<int>(n, 1));
  for (int len = n; len >= 1; len--) {
    q1.init(-2*len, len);
    q2.init(-2*len, len);
    while (q1.position + 1 < n) {
      q1.move();
      q2.move();
      if (q2.takenSum * 2 >= n) {
        if (q1.takenSum <= ansMinAtHome) {
          ansMinAtHome = q1.takenSum;
          ansStart = q1.position;
          ansLen = len;
        }
      }
    }
  }
  printf("%d %d %d", ansMinAtHome, ansLen, ansStart);
}