Submission #670611

#	Time	Username	Problem	Language	Result	Execution time	Memory
670611		rainboy	Harvest (JOI20_harvest)	C11	100 / 100	358 ms	72164 KiB

harvest

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

#define N	200000
#define M	200000
#define Q	200000

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int aa[N], pp[N], ww[N], n; char cycle[N];
int bb[M], jj[M], tt[M], m; long long vv[M];
int ii[Q], q; long long ss[Q], uu[Q], ans[Q];
long long rr[M + Q], l_;
int l, c;

long long *xx;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (xx[ii[j]] == xx[i_])
				j++;
			else if (xx[ii[j]] < xx[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int *ej[N], eo[N], *eg[N], eo_[N], *eh[N], eo1[N];

void append(int **ej, int *eo, int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

char visited[N]; long long dd[N]; int ta[N], tb[N];
int gg[M], m_;
int hh[Q], q_;
int gh[M + Q];

void dfs(int i, long long d) {
	static int time;
	int o;

	if (visited[i] == 1)
		return;
	ta[i] = time++;
	visited[i] = 1;
	dd[i] = d;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs(j, d + ww[j]);
	}
	for (o = eo_[i]; o--; ) {
		int g = eg[i][o];

		gg[m_++] = g;
	}
	for (o = eo1[i]; o--; ) {
		int h = eh[i][o];

		hh[q_++] = h;
	}
	tb[i] = time;
}

int ft[M + Q];

void update(int i, int n, int x) {
	while (i < n) {
		ft[i] += x;
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

void solve1() {
	int g, g_, h, h_;

	for (g = 0, h = 0; h < q_; h++) {
		h_ = hh[h];
		while (g < m_ && uu[g_ = gg[g]] <= vv[h_])
			update(ta[jj[g_]], n, 1), g++;
		ans[h_] += query(tb[ii[h_]] - 1) - query(ta[ii[h_]] - 1);
	}
	while (g--) {
		g_ = gg[g];
		update(ta[jj[g_]], n, -1);
	}
}

void solve2() {
	long long sum, cnt;
	int g, g_, h, h_, r;

	sum = cnt = 0;
	for (g = 0, h = 0; h < q_; h++) {
		h_ = hh[h];
		if (!cycle[ii[h_]])
			continue;
		while (g < m_ && uu[g_ = gg[g]] <= vv[h_])
			sum += uu[g_] / l_, cnt++, g++;
		ans[h_] += vv[h_] / l_ * cnt - sum;
	}
	for (g = 0; g < m_; g++) {
		g_ = gg[g];
		rr[g] = uu[g_] % l_;
	}
	for (h = 0; h < q_; h++) {
		h_ = hh[h];
		rr[m_ + h] = vv[h_] % l_;
	}
	for (g = 0; g < m_ + q_; g++)
		gh[g] = g;
	xx = rr, sort(gh, 0, m_ + q_);
	for (g = 0, r = 0; g < m_ + q_; g++)
		rr[gh[g]] = g + 1 == m_ + q || rr[gh[g + 1]] != rr[gh[g]] ? r++ : r;
	for (g = 0, h = 0; h < q_; h++) {
		h_ = hh[h];
		if (!cycle[ii[h_]])
			continue;
		while (g < m_ && uu[gg[g]] <= vv[h_])
			update(m_ + q_ - 1 - rr[g++], m_ + q_, 1);
		ans[h_] -= query(m_ + q_ - 2 - rr[m_ + h]);
	}
	while (g--)
		update(m_ + q_ - 1 - rr[g], m_ + q_, -1);
}

int main() {
	int g, g_, h, h_, i, i_, j;

	scanf("%d%d%d%d", &n, &m, &l, &c);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (g = 0; g < m; g++)
		scanf("%d", &bb[g]);
	for (i = 0; i < n; i++) {
		eg[i] = (int *) malloc(2 * sizeof *eg[i]);
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	}
	scanf("%d", &q);
	for (h = 0; h < q; h++) {
		scanf("%d%lld", &i, &ss[h]), i--;
		ii[h] = i, append(eh, eo1, i, h);
	}
	for (i = n - 1, j = n - 1; j >= 0; j--) {
		while (aa[j] - (i >= 0 ? aa[i] : aa[i + n] - l) < c % l)
			i--;
		pp[j] = (i + n) % n, ww[j] = c / l * l + aa[j] - (i >= 0 ? aa[i] : aa[i + n] - l);
	}
	for (i = 0, g = 0; g < m; g++) {
		while (i < n && aa[i] < bb[g])
			i++;
		jj[g] = (i - 1 + n) % n, tt[g] = i == 0 ? bb[g] - aa[n - 1] + l : bb[g] - aa[i - 1];
		append(eg, eo_, jj[g], g);
	}
	for (i = 0; i < n; i++)
		append(ej, eo, pp[i], i);
	for (i = 0; i < n; i++) {
		if (visited[i])
			continue;
		i_ = i;
		while (!visited[i_])
			visited[i_] = -1, i_ = pp[i_];
		l_ = 0;
		while (!cycle[i_])
			l_ += ww[i_], cycle[i_] = 1, i_ = pp[i_];
		m_ = q_ = 0;
		dfs(i_, 0);
		for (g = 0; g < m_; g++) {
			g_ = gg[g];
			uu[g_] = dd[jj[g_]] + tt[g_];
		}
		for (h = 0; h < q_; h++) {
			h_ = hh[h];
			vv[h_] = dd[ii[h_]] + ss[h_];
		}
		xx = uu, sort(gg, 0, m_);
		xx = vv, sort(hh, 0, q_);
		solve1();
		solve2();
	}
	for (h = 0; h < q; h++)
		printf("%lld\n", ans[h]);
	return 0;
}

Compilation message (stderr)

harvest.c: In function 'append':
harvest.c:46:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   46 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
harvest.c: In function 'main':
harvest.c:158:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |  scanf("%d%d%d%d", &n, &m, &l, &c);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.c:160:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
harvest.c:162:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |   scanf("%d", &bb[g]);
      |   ^~~~~~~~~~~~~~~~~~~
harvest.c:168:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
harvest.c:170:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |   scanf("%d%lld", &i, &ss[h]), i--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 75 / 75