Submission #869793

# Submission time Handle Problem Language Result Execution time Memory
869793 2023-11-05T17:19:25 Z rainboy Simple (info1cup19_simple) C
60 / 100
1000 ms 24124 KB
#include <stdio.h>
 
#define N	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N))) */
#define INF	0x3f3f3f3f3f3f3f3fLL
#define min(a, b)	((a) < (b) ? (a) : (b))
#define max(a, b)	((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:102:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
subway.c:104:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
subway.c:106:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
subway.c:111:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   scanf("%d%d%d", &t, &l, &r), l--, r--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
subway.c:113:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |    scanf("%lld", &x);
      |    ^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 5 ms 8540 KB Output is correct
2 Correct 4 ms 8628 KB Output is correct
3 Correct 6 ms 8540 KB Output is correct
4 Correct 5 ms 8800 KB Output is correct
5 Correct 5 ms 8540 KB Output is correct
6 Correct 6 ms 8712 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 62 ms 19096 KB Output is correct
2 Correct 123 ms 21076 KB Output is correct
3 Correct 124 ms 21076 KB Output is correct
4 Correct 129 ms 21324 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 8540 KB Output is correct
2 Correct 4 ms 8628 KB Output is correct
3 Correct 6 ms 8540 KB Output is correct
4 Correct 5 ms 8800 KB Output is correct
5 Correct 5 ms 8540 KB Output is correct
6 Correct 6 ms 8712 KB Output is correct
7 Correct 62 ms 19096 KB Output is correct
8 Correct 123 ms 21076 KB Output is correct
9 Correct 124 ms 21076 KB Output is correct
10 Correct 129 ms 21324 KB Output is correct
11 Correct 103 ms 19792 KB Output is correct
12 Correct 295 ms 21844 KB Output is correct
13 Correct 235 ms 23392 KB Output is correct
14 Correct 276 ms 22008 KB Output is correct
15 Correct 196 ms 24124 KB Output is correct
16 Execution timed out 1069 ms 17912 KB Time limit exceeded
17 Halted 0 ms 0 KB -