oj.uz

답안 #869802

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
869802 2023-11-05T17:41:16 Z rainboy Simple (info1cup19_simple) C
100 / 100
 265 ms 26432 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 st[N_ * 2][5]; int h_, n_;
 
void put(int i, long long x) {
	long long tmp;
 
	if (st[i][0] != INF)
		st[i][0] += x;
	if (st[i][1] != -1)
		st[i][1] += x;
	if (st[i][2] != INF)
		st[i][2] += x;
	if (st[i][3] != -1)
		st[i][3] += x;
	if (x % 2 != 0) {
		tmp = st[i][0], st[i][0] = st[i][2], st[i][2] = tmp;
		tmp = st[i][1], st[i][1] = st[i][3], st[i][3] = tmp;
	}
	if (i < n_)
		st[i][4] += x;
}
 
void pus(int i) {
	if (st[i][4])
		put(i << 1 | 0, st[i][4]), put(i << 1 | 1, st[i][4]), st[i][4] = 0;
}
 
void pul(int i) {
	if (!st[i][4]) {
		int l = i << 1, r = l | 1;
 
		st[i][0] = min(st[l][0], st[r][0]), st[i][1] = max(st[l][1], st[r][1]);
		st[i][2] = min(st[l][2], st[r][2]), st[i][3] = max(st[l][3], st[r][3]);
	}
}
 
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)
			st[n_ + i][0] = a, st[n_ + i][1] = a, st[n_ + i][2] = INF, st[n_ + i][3] = -1;
		else
			st[n_ + i][0] = INF, st[n_ + i][1] = -1, st[n_ + i][2] = a, st[n_ + i][3] = 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, st[l][0]), *y = max(*y, st[l][3]), l++;
		if ((r & 1) == 0)
			*x = min(*x, st[r][0]), *y = max(*y, st[r][3]), 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 4 ms 604 KB Output is correct
2 Correct 3 ms 816 KB Output is correct
3 Correct 5 ms 1116 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 4 ms 1112 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 13856 KB Output is correct
2 Correct 142 ms 25192 KB Output is correct
3 Correct 140 ms 25036 KB Output is correct
4 Correct 143 ms 25168 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 3 ms 816 KB Output is correct
3 Correct 5 ms 1116 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 4 ms 1112 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 59 ms 13856 KB Output is correct
8 Correct 142 ms 25192 KB Output is correct
9 Correct 140 ms 25036 KB Output is correct
10 Correct 143 ms 25168 KB Output is correct
11 Correct 98 ms 13996 KB Output is correct
12 Correct 265 ms 24388 KB Output is correct
13 Correct 240 ms 25760 KB Output is correct
14 Correct 233 ms 24404 KB Output is correct
15 Correct 190 ms 26432 KB Output is correct
16 Correct 145 ms 21596 KB Output is correct