oj.uz

답안 #869789

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
869789 2023-11-05T16:45:14 Z rainboy Simple (info1cup19_simple) C
60 / 100
 1000 ms 29380 KB 
#include <stdio.h>

#define N	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N))) */
#define INF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

long long stmn0[N_ * 2], stmn1[N_ * 2], stmx0[N_ * 2], stmx1[N_ * 2], lz[N_]; int h_, n_;

void put(int i, long long x) {
	long long tmp;

	if (stmn0[i] != INF)
		stmn0[i] += x;
	if (stmx0[i] != -1)
		stmx0[i] += x;
	if (stmn1[i] != INF)
		stmn1[i] += x;
	if (stmx1[i] != -1)
		stmx1[i] += x;
	if (x % 2 != 0) {
		tmp = stmn0[i], stmn0[i] = stmn1[i], stmn1[i] = tmp;
		tmp = stmx0[i], stmx0[i] = stmx1[i], stmx1[i] = tmp;
	}
	if (i < n_)
		lz[i] += x;
}

void pus(int i) {
	if (lz[i])
		put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = 0;
}

void pul(int i) {
	if (!lz[i]) {
		int l = i << 1, r = l | 1;

		stmn0[i] = min(stmn0[l], stmn0[r]), stmx0[i] = max(stmx0[l], stmx0[r]);
		stmn1[i] = min(stmn1[l], stmn1[r]), stmx1[i] = max(stmx1[l], stmx1[r]);
	}
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

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

	h_ = 0;
	while (1 << h_ < n)
		h_++;
	n_ = 1 << h_;
	for (i = 0; i < n_; i++) {
		a = i < n ? aa[i] : 0;
		if (a % 2 == 0)
			stmn0[n_ + i] = a, stmx0[n_ + i] = a, stmn1[n_ + i] = INF, stmx1[n_ + i] = -1;
		else
			stmn0[n_ + i] = INF, stmx0[n_ + i] = -1, stmn1[n_ + i] = a, stmx1[n_ + i] = a;
	}
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

void update(int l, int r, int x) {
	int l_ = l += n_, r_ = r += n_;

	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, x);
		if ((r & 1) == 0)
			put(r--, x);
	}
	pull(l_), pull(r_);
}

void query(int l, int r, long long *x, long long *y) {
	push(l += n_), push(r += n_);
	*x = INF, *y = -1;
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			*x = min(*x, stmn0[l]), *y = max(*y, stmx1[l]), l++;
		if ((r & 1) == 0)
			*x = min(*x, stmn0[r]), *y = max(*y, stmx1[r]), r--;
	}
}

int main() {
	static int aa[N];
	int n, q, i;

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

		scanf("%d%d%d", &t, &l, &r), l--, r--;
		if (t == 0) {
			scanf("%lld", &x);
			update(l, r, x);
		} else {
			query(l, r, &x, &y);
			if (x == INF)
				x = -1;
			printf("%lld %lld\n", x, y);
		}
	}
	return 0;
}

Compilation message

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

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8796 KB Output is correct
2 Correct 5 ms 8796 KB Output is correct
3 Correct 6 ms 8796 KB Output is correct
4 Correct 5 ms 8796 KB Output is correct
5 Correct 5 ms 8796 KB Output is correct
6 Correct 5 ms 8812 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 21328 KB Output is correct
2 Correct 126 ms 25936 KB Output is correct
3 Correct 127 ms 25936 KB Output is correct
4 Correct 124 ms 26108 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8796 KB Output is correct
2 Correct 5 ms 8796 KB Output is correct
3 Correct 6 ms 8796 KB Output is correct
4 Correct 5 ms 8796 KB Output is correct
5 Correct 5 ms 8796 KB Output is correct
6 Correct 5 ms 8812 KB Output is correct
7 Correct 60 ms 21328 KB Output is correct
8 Correct 126 ms 25936 KB Output is correct
9 Correct 127 ms 25936 KB Output is correct
10 Correct 124 ms 26108 KB Output is correct
11 Correct 109 ms 22540 KB Output is correct
12 Correct 296 ms 28044 KB Output is correct
13 Correct 239 ms 28756 KB Output is correct
14 Correct 277 ms 28036 KB Output is correct
15 Correct 215 ms 29380 KB Output is correct
16 Execution timed out 1039 ms 23564 KB Time limit exceeded
17 Halted 0 ms 0 KB -