oj.uz

Submission #1004125

# Submission time Handle Problem Language Result Execution time Memory
1004125 2024-06-21T05:37:04 Z coolboy19521 Horses (IOI15_horses) C++17
17 / 100
 37 ms 27872 KB 
#include "bits/stdc++.h"
#include "horses.h"
#define i64 long long

using namespace std;

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

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

void build(int le, int ri, int v) {
	if (le == ri) {
		st[v] = c[le] * b[le];
		return;
	}
	int 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(int v) {
	st[v] *= lzm[v];
	st[v] /= lzd[v];
	lzm[v * 2] *= lzm[v];
	lzm[v * 2 + 1] *= lzm[v];
	lzd[v * 2] *= lzd[v];
	lzd[v * 2 + 1] *= lzd[v];
	lzm[v] = lzd[v] = 0;
}

void rupdate(int le, int ri, int ql, int qr, int v, i64 m, i64 d) {
	if (le > qr || ri < ql) return;
	if (ql <= le && ri <= qr) {
		lzm[v] = m;
		lzd[v] = d;
		relax(v);
		return;
	}
	int 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(int le, int ri, int ix, int v, i64 m, i64 d) {
	if (le > ix || ri < ix) return;
	if (le == ix && ix == ri) {
		st[v] /= d;
		st[v] *= m;
		return;
	}
	int 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(int le, int ri, int ql, int qr, int v) {
	if (le > qr || ri < ql) {
		return -inf;
	}
	if (0 != lzm[v] && 0 != lzd[v]) {
		relax(v);
	}
	if (ql <= le && ri <= qr) {
		return st[v];
	}
	int 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];
	}

	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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 0 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 0 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6744 KB Output is correct
11 Correct 0 ms 6492 KB Output is correct
12 Correct 0 ms 6492 KB Output is correct
13 Correct 0 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6596 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Incorrect 1 ms 8540 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 27872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Incorrect 1 ms 8540 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 0 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6588 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Incorrect 1 ms 8540 KB Output isn't correct
22 Halted 0 ms 0 KB -