oj.uz

답안 #471236

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
471236 2021-09-07T19:48:05 Z rainboy Garaža (COCI17_garaza) C
160 / 160
 667 ms 137000 KB 
#include <stdio.h>
#include <string.h>

#define N	100000
#define N_	(1 << 17)	/* N_ = pow2(ceil(log2(N))) */
#define K	32

int aa[N];
int n_; long long cnt[N_ * 2];
int pp[N_ * 2][K], cp[N_ * 2][K], nnp[N_ * 2];
int qq[N_ * 2][K], cq[N_ * 2][K], nnq[N_ * 2];

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

long long solve(int *aa, int *cc, int n, int *bb, int *dd, int m) {
	int i, j, d;
	long long ans;

	d = 0, ans = 0;
	for (i = n - 1, j = 0, d = 0; i >= 0; i--) {
		int a = aa[i] / (i + 1 == n ? 1 : aa[i + 1]);

		while (j < m && gcd(a, bb[j]) > 1)
			d += dd[j++];
		ans += (long long) cc[i] * d;
	}
	return ans;
}

int merge(int *aa, int *cc, int n, int *bb, int *dd, int m, int *ab, int *cd) {
	int j, k, a;

	memcpy(ab, aa, n * sizeof *aa), memcpy(cd, cc, n * sizeof *cc);
	a = aa[n - 1], k = n;
	for (j = 0; j < m; j++) {
		a = gcd(a, bb[j]);
		if (ab[k - 1] != a)
			ab[k] = a, cd[k] = dd[j], k++;
		else
			cd[k - 1] += dd[j];
	}
	return k;
}

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

	cnt[i] = cnt[l] + solve(qq[l], cq[l], nnq[l], pp[r], cp[r], nnp[r]) + cnt[r];
	nnp[i] = merge(pp[l], cp[l], nnp[l], pp[r], cp[r], nnp[r], pp[i], cp[i]);
	nnq[i] = merge(qq[r], cq[r], nnq[r], qq[l], cq[l], nnq[l], qq[i], cq[i]);
}

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

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n_; i++) {
		int a = i < n ? aa[i] : 1;

		cnt[n_ + i] = a == 1 ? 0 : 1;
		pp[n_ + i][0] = a, cp[n_ + i][0] = 1, nnp[n_ + i] = 1;
		qq[n_ + i][0] = a, cq[n_ + i][0] = 1, nnq[n_ + i] = 1;
	}
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

void update(int i, int x) {
	cnt[n_ + i] = x == 1 ? 0 : 1;
	pp[n_ + i][0] = x, cp[n_ + i][0] = 1;
	qq[n_ + i][0] = x, cq[n_ + i][0] = 1;
	i += n_;
	while (i > 1)
		pul(i >>= 1);
}

long long query(int l, int r) {
	static int pp_[K], cp_[K], qq_[K], cq_[K], pp1[K], cp1[K], qq1[K], cq1[K];
	int np, nq;
	long long cntl, cntr;

	np = nq = 0, cntl = cntr = 0;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1) {
			cntl += solve(qq_, cq_, nq, pp[l], cp[l], nnp[l]) + cnt[l];
			nq = merge(qq[l], cq[l], nnq[l], qq_, cq_, nq, qq1, cq1);
			memcpy(qq_, qq1, nq * sizeof *qq1), memcpy(cq_, cq1, nq * sizeof *cq1);
			l++;
		}
		if ((r & 1) == 0) {
			cntr += cnt[r] + solve(qq[r], cq[r], nnq[r], pp_, cp_, np);
			np = merge(pp[r], cp[r], nnp[r], pp_, cp_, np, pp1, cp1);
			memcpy(pp_, pp1, np * sizeof *pp1), memcpy(cp_, cp1, np * sizeof *cp1);
			r--;
		}
	}
	return cntl + solve(qq_, cq_, nq, pp_, cp_, np) + cntr;
}

int main() {
	int n, q, i;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	build(aa, n);
	while (q--) {
		int t;

		scanf("%d", &t);
		if (t == 1) {
			int x;

			scanf("%d%d", &i, &x), i--;
			update(i, x);
			aa[i] = x;
		} else {
			int l, r;

			scanf("%d%d", &l, &r), l--, r--;
			printf("%lld\n", query(l, r));
		}
	}
	return 0;
}

Compilation message

garaza.c: In function 'main':
garaza.c:107:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
garaza.c:109:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
garaza.c:114:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |   scanf("%d", &t);
      |   ^~~~~~~~~~~~~~~
garaza.c:118:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |    scanf("%d%d", &i, &x), i--;
      |    ^~~~~~~~~~~~~~~~~~~~~
garaza.c:124:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |    scanf("%d%d", &l, &r), l--, r--;
      |    ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1356 KB Output is correct
2 Correct 10 ms 4584 KB Output is correct
3 Correct 21 ms 8824 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 34264 KB Output is correct
2 Correct 138 ms 34520 KB Output is correct
3 Correct 187 ms 34488 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 309 ms 68360 KB Output is correct
2 Correct 360 ms 68504 KB Output is correct
3 Correct 359 ms 68412 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 522 ms 137000 KB Output is correct
2 Correct 657 ms 136544 KB Output is correct
3 Correct 667 ms 136480 KB Output is correct