Submission #483310

#	Time	Username	Problem	Language	Result	Execution time	Memory
483310		rainboy	Specijacija (COCI20_specijacija)	C11	110 / 110	1824 ms	41624 KiB

Main

#include <stdio.h>
#include <stdlib.h>

#define N	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N + 2))) */
#define K	100

int n;

int depth(long long i) {
	int lower = -1, upper = n;

	while (upper - lower > 1) {
		int d = (lower + upper) / 2;

		if (i < (long long) (d + 1) * (d + 2) / 2)
			upper = d;
		else
			lower = d;
	}
	return upper;
}

int *aaa[N_ * 2], sz[N_ * 2], n_;

void pul(int i) {
	int l = i << 1, r = l | 1, hl, hr, h;

	aaa[i] = (int *) malloc((sz[i] = sz[l] + sz[r]) * sizeof *aaa[i]);
	hl = 0, hr = 0, h = 0;
	while (hl < sz[l] && hr < sz[r])
		if (aaa[l][hl] + hr < aaa[r][hr])
			aaa[i][h++] = aaa[l][hl++] + hr;
		else
			aaa[i][h++] = aaa[r][hr++];
	while (hl < sz[l])
		aaa[i][h++] = aaa[l][hl++] + hr;
	while (hr < sz[r])
		aaa[i][h++] = aaa[r][hr++];
}

void build(int *aa, int n) {
	int i;

	n_ = 1;
	while (n_ < n + 2)
		n_ <<= 1;
	for (i = 0; i < n_; i++)
		if (i >= n)
			sz[n_ + i] = 0;
		else {
			aaa[n_ + i] = (int *) malloc((sz[n_ + i] = 1) * sizeof *aaa[n_ + i]);
			aaa[n_ + i][0] = aa[i];
		}
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

int lift(int i, int a) {
	int lower = -1, upper = sz[i];

	while (upper - lower > 1) {
		int h = (lower + upper) / 2;

		if (aaa[i][h] < a)
			lower = h;
		else
			upper = h;
	}
	return a - upper;
}

int lift1(int l, int r, int a) {
	static int qu[K];
	int cnt;

	cnt = 0;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			qu[cnt++] = l++;
		if ((r & 1) == 0)
			a = lift(r--, a);
	}
	while (cnt--)
		a = lift(qu[cnt], a);
	return a;
}

long long lift2(int r, int a, int b) {
	int l = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0) {
			int i = r--, a_ = lift(i, a), b_ = lift(i, b);

			if (a_ != b_)
				a = a_, b = b_;
			else {
				while (i < n_) {
					a_ = lift(i << 1 | 1, a), b_ = lift(i << 1 | 1, b);
					if (a_ != b_)
						a = a_, b = b_, i = i << 1 | 0;
					else
						i = i << 1 | 1;
				}
				return (long long) (i - n_) * (i - n_ + 1) / 2 + lift(i, a);
			}
		}
	return -1;
}

int main() {
	static int ii[N];
	int q, t, i, j;
	long long n1, ans;

	scanf("%d%d%d", &n, &q, &t);
	for (i = 0; i < n; i++) {
		long long a;

		scanf("%lld", &a), a--, ii[i] = a - (long long) i * (i + 1) / 2;
	}
	build(ii, n);
	n1 = (long long) (n + 1) * (n + 2) / 2, ans = 0;
	while (q--) {
		long long x, y, tmp;
		int dx, dy;

		scanf("%lld%lld", &x, &y), x--, y--;
		x = (x + t * ans) % n1, y = (y + t * ans) % n1;
		if (x > y)
			tmp = x, x = y, y = tmp;
		dx = depth(x), i = x - (long long) dx * (dx + 1) / 2;
		dy = depth(y), j = y - (long long) dy * (dy + 1) / 2;
		j = lift1(dx, dy - 1, j);
		printf("%lld\n", ans = (i == j ? (long long) dx * (dx + 1) / 2 + i : lift2(dx - 1, i, j)) + 1);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:117:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |  scanf("%d%d%d", &n, &q, &t);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:121:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |   scanf("%lld", &a), a--, ii[i] = a - (long long) i * (i + 1) / 2;
      |   ^~~~~~~~~~~~~~~~~
Main.c:129:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |   scanf("%lld%lld", &x, &y), x--, y--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60