답안 #1004312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1004312	2024-06-21T07:35:55 Z	vjudge1	말 (IOI15_horses)	C++17	17 / 100	126 ms	107736 KB

horses

#include "bits/stdc++.h"
#include "horses.h"
#define i64 __int128

using namespace std;

const i64 sz = 5e5 + 25;
const i64 md = 1e9 + 7;

i64 lzm[sz * 4], lzd[sz * 4];
i64 a[sz], b[sz], c[sz];
i64 st[sz * 4];
i64 n;

void build(i64 le, i64 ri, i64 v) {
	if (le == ri) {
		st[v] = c[le] * b[le];
		return;
	}
	i64 mi = le + (ri - le) / 2;
	build(le, mi, v * 2);
	build(mi + 1, ri, v * 2 + 1);
	st[v] = max(st[v * 2], st[v * 2 + 1]);
}

void relax(i64 v) {
	st[v] *= lzm[v];
	st[v] /= lzd[v];
	if (v * 2 < sz * 4) {
		lzm[v * 2] *= lzm[v];
		lzd[v * 2] *= lzd[v];
	}
	if (v * 2 + 1 < sz * 4) {
		lzm[v * 2 + 1] *= lzm[v];
		lzd[v * 2 + 1] *= lzd[v];
	}
	lzm[v] = lzd[v] = 1;
}

void rupdate(i64 le, i64 ri, i64 ql, i64 qr, i64 v, i64 m, i64 d) {
	relax(v);
	if (le > qr || ri < ql) return;
	if (ql <= le && ri <= qr) {
		lzm[v] = m;
		lzd[v] = d;
		relax(v);
		return;
	}
	i64 mi = le + (ri - le) / 2;
	rupdate(le, mi, ql, qr, v * 2, m, d);
	rupdate(mi + 1, ri, ql, qr, v * 2 + 1, m, d);
	st[v] = max(st[v * 2], st[v * 2 + 1]);
}

void pupdate(i64 le, i64 ri, i64 ix, i64 v, i64 m, i64 d) {
	relax(v);
	if (le > ix || ri < ix) return;
	if (le == ix && ix == ri) {
		st[v] *= m;
		st[v] /= d;
		return;
	}
	i64 mi = le + (ri - le) / 2;
	pupdate(le, mi, ix, v * 2, m, d);
	pupdate(mi + 1, ri, ix, v * 2 + 1, m, d);
	st[v] = max(st[v * 2], st[v * 2 + 1]);
}

i64 query(i64 le, i64 ri, i64 ql, i64 qr, i64 v) {
	relax(v);
	if (le > qr || ri < ql) {
		return 0;
	}
	if (ql <= le && ri <= qr) {
		return st[v];
	}
	i64 mi = le + (ri - le) / 2;
	i64 lq = query(le, mi, ql, qr, v * 2);
	i64 rq = query(mi + 1, ri, ql, qr, v * 2 + 1);
	return max(lq, rq);
}

int init(int N, int X[], int Y[]) {
	c[0] = 1;
	n = N;

	for (int i = 1; i <= N; i ++) {
		c[i] = c[i - 1] * X[i - 1];
		a[i] = X[i - 1];
		b[i] = Y[i - 1];
	}

	for (int i = 0; i < sz * 4; i ++) {
		lzm[i] = lzd[i] = 1;
	}

	build(1, N, 1);

	i64 r = query(1, n, 1, n, 1) % md;

	return (int) r;
}

int updateX(int pos, int val) {	
	pos ++;
	rupdate(1, n, pos, n, 1, val, a[pos]);
	a[pos] = val;
	i64 r = query(1, n, 1, n, 1) % md;
	return (int) r;
}

int updateY(int pos, int val) {
	pos ++;
	pupdate(1, n, pos, 1, val, b[pos]);
	b[pos] = val;
	i64 r = query(1, n, 1, n, 1) % md;
	return (int) r;
}

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	63068 KB	Output is correct
2	Correct	23 ms	62912 KB	Output is correct
3	Correct	22 ms	63068 KB	Output is correct
4	Correct	23 ms	63068 KB	Output is correct
5	Correct	21 ms	63100 KB	Output is correct
6	Correct	22 ms	63056 KB	Output is correct
7	Correct	22 ms	63068 KB	Output is correct
8	Correct	21 ms	63072 KB	Output is correct
9	Correct	22 ms	63068 KB	Output is correct
10	Correct	20 ms	63028 KB	Output is correct
11	Correct	22 ms	63068 KB	Output is correct
12	Correct	20 ms	63068 KB	Output is correct
13	Correct	21 ms	63064 KB	Output is correct
14	Correct	23 ms	63064 KB	Output is correct
15	Correct	20 ms	63068 KB	Output is correct
16	Correct	21 ms	63068 KB	Output is correct
17	Correct	21 ms	63064 KB	Output is correct
18	Correct	22 ms	63064 KB	Output is correct
19	Correct	24 ms	63068 KB	Output is correct
20	Correct	21 ms	63064 KB	Output is correct

Subtask #2
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	63068 KB	Output is correct
2	Correct	20 ms	63064 KB	Output is correct
3	Correct	21 ms	63064 KB	Output is correct
4	Correct	22 ms	63068 KB	Output is correct
5	Correct	22 ms	62972 KB	Output is correct
6	Correct	22 ms	63068 KB	Output is correct
7	Correct	23 ms	63068 KB	Output is correct
8	Correct	22 ms	63064 KB	Output is correct
9	Correct	21 ms	63068 KB	Output is correct
10	Correct	20 ms	63068 KB	Output is correct
11	Correct	22 ms	63064 KB	Output is correct
12	Correct	25 ms	62916 KB	Output is correct
13	Correct	24 ms	63068 KB	Output is correct
14	Correct	21 ms	63068 KB	Output is correct
15	Correct	21 ms	63068 KB	Output is correct
16	Correct	21 ms	63068 KB	Output is correct
17	Correct	26 ms	63068 KB	Output is correct
18	Correct	22 ms	63068 KB	Output is correct
19	Correct	22 ms	63064 KB	Output is correct
20	Correct	20 ms	62996 KB	Output is correct
21	Correct	23 ms	63068 KB	Output is correct
22	Correct	23 ms	62996 KB	Output is correct
23	Incorrect	22 ms	63068 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #3
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	126 ms	107736 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	63068 KB	Output is correct
2	Correct	25 ms	62948 KB	Output is correct
3	Correct	21 ms	63064 KB	Output is correct
4	Correct	21 ms	63032 KB	Output is correct
5	Correct	21 ms	63068 KB	Output is correct
6	Correct	21 ms	62908 KB	Output is correct
7	Correct	20 ms	63068 KB	Output is correct
8	Correct	22 ms	63064 KB	Output is correct
9	Correct	20 ms	63320 KB	Output is correct
10	Correct	20 ms	63068 KB	Output is correct
11	Correct	23 ms	63064 KB	Output is correct
12	Correct	23 ms	63064 KB	Output is correct
13	Correct	25 ms	63056 KB	Output is correct
14	Correct	21 ms	63064 KB	Output is correct
15	Correct	22 ms	63068 KB	Output is correct
16	Correct	23 ms	63028 KB	Output is correct
17	Correct	21 ms	63076 KB	Output is correct
18	Correct	22 ms	63068 KB	Output is correct
19	Correct	21 ms	63068 KB	Output is correct
20	Correct	21 ms	63068 KB	Output is correct
21	Correct	21 ms	63064 KB	Output is correct
22	Correct	22 ms	63068 KB	Output is correct
23	Incorrect	23 ms	63056 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	63068 KB	Output is correct
2	Correct	21 ms	62908 KB	Output is correct
3	Correct	21 ms	63068 KB	Output is correct
4	Correct	21 ms	63068 KB	Output is correct
5	Correct	22 ms	63068 KB	Output is correct
6	Correct	21 ms	63068 KB	Output is correct
7	Correct	21 ms	62872 KB	Output is correct
8	Correct	25 ms	63064 KB	Output is correct
9	Correct	21 ms	63064 KB	Output is correct
10	Correct	21 ms	63056 KB	Output is correct
11	Correct	22 ms	62992 KB	Output is correct
12	Correct	21 ms	63068 KB	Output is correct
13	Correct	28 ms	63068 KB	Output is correct
14	Correct	21 ms	63320 KB	Output is correct
15	Correct	22 ms	62972 KB	Output is correct
16	Correct	20 ms	63068 KB	Output is correct
17	Correct	21 ms	63056 KB	Output is correct
18	Correct	21 ms	63060 KB	Output is correct
19	Correct	21 ms	63068 KB	Output is correct
20	Correct	20 ms	63072 KB	Output is correct
21	Correct	21 ms	63068 KB	Output is correct
22	Correct	21 ms	63072 KB	Output is correct
23	Incorrect	22 ms	63060 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

답안 #1004312

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 0 / 17.0

Subtask #3 0 / 20.0

Subtask #4 0 / 23.0

Subtask #5 0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
0 / 17.0

Subtask #3
0 / 20.0

Subtask #4
0 / 23.0

Subtask #5
0 / 23.0