1491I - Ruler Of The Zoo - CodeForces Solution

#include <stdio.h>
#define N	6000
int min(int a, int b) { return a < b ? a : b; }
void rotate(int *ii, int n, int i) {static int jj[N];int h;for (h = 0; h < n; h++)jj[h] = ii[(i + h) % n];for (h = 0; h < n; h++)ii[h] = jj[h];}
int main() {static int aa[N], bb[N], cc[N], ii[N], gap[N], jj[N * 2], qu[N * 2];int n, h, i, j, k, tmp, circle, head, cnt;long long t;scanf("%d", &n);
	for (i = 0; i < n; i++) {scanf("%d%d%d", &aa[i], &bb[i], &cc[i]);ii[i] = i;}t = 1;if (aa[0] > aa[1])k = 0, tmp = ii[0], ii[0] = ii[1], ii[1] = tmp;else	k = 1;
	while (1) {int n_, r, r_, l, l_;circle = 1;for (i = 0; i < n; i++) {gap[i] = bb[ii[i]] > aa[ii[(i + 1) % n]];circle = circle && !gap[i];}
		if (circle) {printf("-1 -1\n");return 0;}for (i = 0; i < n; i++)if (ii[i] == k)break;while (!gap[i])i = (i + 1) % n, t++;rotate(ii, n, i), rotate(gap, n, i);
		for (j = 0; j < n - 1; j++)if (gap[j] && (j == n - 2 || cc[ii[j]] > aa[ii[j + 2]])) {printf("%d %lld\n", ii[j], t + j + 2);return 0;}r_ = l_ = n + 3;
		for (j = n - 1, l = n; j > 0; j--)if (!gap[j - 1]) {if (!gap[j] && cc[ii[j]] > aa[ii[j + 1]])if (r_ > l - j || r_ == l - j && l_ > l % n)r_ = l - j, l_ = l % n;
			} else		l = j - 1;n_ = 0, head = cnt = 0, r = r_ + 1;for (j = 0; j < n; j++)if (j == 0 || !gap[j - 1]) {jj[n_++] = j;
				while (cnt && bb[ii[jj[qu[head + cnt - 1]]]] > bb[ii[jj[n_ - 1]]])cnt--;qu[head + cnt++] = n_ - 1;}for (j = 0; j < n; j++)if (j == 0 || !gap[j - 1]) {
				jj[n_++] = j;while (cnt && bb[ii[jj[qu[head + cnt - 1]]]] > bb[ii[jj[n_ - 1]]])cnt--;qu[head + cnt++] = n_ - 1;} else
				while (cnt && bb[ii[jj[qu[head]]]] < aa[ii[j]]) {r = min(r, n_ - 1 - qu[head]);head++, cnt--;}
		if (r == r_ + 1) {if (r_ == n + 3)printf("-1 -1\n");else		printf("%d %lld\n", l_ == 0 ? ii[n - r_] : ii[l_ - r_], t + r_ * (n - 1) + l_ + 2);return 0;}
		for (h = 0; h < n_; h++)jj[h] = ii[jj[h]];for (j = 0, h = n_ / 2 - r; j < n; j++)if (j == 0 || !gap[j - 1])ii[j] = jj[h++];k = ii[0], t += r * (n - 1);}return 0;}