답안 #545936

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545936	2022-04-05T16:14:13 Z	rainboy	Fancy Fence (CEOI20_fancyfence)	C	100 / 100	66 ms	4356 KB

fancyfence

#include <stdio.h>

#define N	100000
#define MD	1000000007

unsigned int X = 12345;

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

int hh[N], ww[N];

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 (hh[ii[j]] == hh[i_])
				j++;
			else if (hh[ii[j]] > hh[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 main() {
	static char used[N];
	static int ii[N], ll[N], rr[N];
	int n, i, ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &hh[i]);
	for (i = 0; i < n; i++)
		scanf("%d", &ww[i]);
	for (i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	ans = 0;
	for (i = 0; i < n; i++)
		ll[i] = rr[i] = i;
	for (i = 0; i < n; i++) {
		int i_, h, l, r;

		i_ = ii[i], h = (long long) hh[i_] * (hh[i_] + 1) / 2 % MD;
		used[i_] = 1, ans = (ans + (long long) ww[i_] * (ww[i_] + 1) / 2 % MD * h) % MD;
		l = r = i_;
		if (i_ > 0 && used[i_ - 1]) {
			l = ll[i_ - 1];
			ans = (ans + (long long) ww[l] * ww[i_] % MD * h) % MD, ww[l] = (ww[l] + ww[i_]) % MD;
			rr[l] = r, ll[r] = l;
		}
		if (i_ + 1 < n && used[i_ + 1]) {
			r = rr[i_ + 1];
			ans = (ans + (long long) ww[l] * ww[i_ + 1] % MD * h) % MD, ww[l] = (ww[l] + ww[i_ + 1]) % MD;
			rr[l] = r, ll[r] = l;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

fancyfence.c: In function 'main':
fancyfence.c:38:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
fancyfence.c:40:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d", &hh[i]);
      |   ^~~~~~~~~~~~~~~~~~~
fancyfence.c:42:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d", &ww[i]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1

0.0 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	292 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	292 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	292 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct

Subtask #3

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	21 ms	1792 KB	Output is correct
4	Correct	39 ms	3476 KB	Output is correct
5	Correct	33 ms	3396 KB	Output is correct
6	Correct	29 ms	3400 KB	Output is correct

Subtask #4

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	5 ms	660 KB	Output is correct
3	Correct	17 ms	2260 KB	Output is correct
4	Correct	42 ms	4148 KB	Output is correct
5	Correct	52 ms	4292 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct

Subtask #5

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	8 ms	692 KB	Output is correct
4	Correct	16 ms	2216 KB	Output is correct
5	Correct	32 ms	4240 KB	Output is correct
6	Correct	32 ms	4356 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	4 ms	688 KB	Output is correct
9	Correct	18 ms	2228 KB	Output is correct
10	Correct	37 ms	4084 KB	Output is correct
11	Correct	38 ms	4236 KB	Output is correct
12	Correct	0 ms	292 KB	Output is correct

Subtask #6

18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	292 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	300 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct
14	Correct	1 ms	316 KB	Output is correct
15	Correct	1 ms	308 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct

Subtask #7

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	292 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	296 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	292 KB	Output is correct
6	Correct	1 ms	300 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	284 KB	Output is correct
9	Correct	1 ms	296 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	15 ms	1868 KB	Output is correct
12	Correct	27 ms	3404 KB	Output is correct
13	Correct	37 ms	3440 KB	Output is correct
14	Correct	28 ms	3364 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	4 ms	596 KB	Output is correct
17	Correct	16 ms	2220 KB	Output is correct
18	Correct	32 ms	4216 KB	Output is correct
19	Correct	33 ms	4244 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	4 ms	672 KB	Output is correct
22	Correct	17 ms	2224 KB	Output is correct
23	Correct	38 ms	4140 KB	Output is correct
24	Correct	37 ms	4236 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	5 ms	688 KB	Output is correct
31	Correct	5 ms	696 KB	Output is correct
32	Correct	17 ms	2100 KB	Output is correct
33	Correct	24 ms	2172 KB	Output is correct
34	Correct	46 ms	4040 KB	Output is correct
35	Correct	36 ms	4012 KB	Output is correct
36	Correct	46 ms	4136 KB	Output is correct
37	Correct	66 ms	4168 KB	Output is correct
38	Correct	1 ms	212 KB	Output is correct
39	Correct	45 ms	4268 KB	Output is correct
40	Correct	45 ms	4212 KB	Output is correct
41	Correct	40 ms	4256 KB	Output is correct
42	Correct	51 ms	4152 KB	Output is correct