oj.uz

Submission #1004153

# Submission time Handle Problem Language Result Execution time Memory
1004153 2024-06-21T05:55:48 Z coolboy19521 Horses (IOI15_horses) C++17
17 / 100
 59 ms 61468 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];
	// cout << st[v] << ' ' << lzm[v] << ' ' << lzd[v] << '\n';
	if (v * 2 < sz * 4) {
		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 (0 != lzm[v] && 0 != lzd[v]) {
		relax(v);
	}
	if (le > qr || ri < ql) return;
	if (ql <= le && ri <= qr) {
		lzm[v] = m;
		lzd[v] = d;
		// cout << "RELAX " << le << ' ' << ri << '\n';
		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 (0 != lzm[v] && 0 != lzd[v]) {
		relax(v);
	}
	if (le > ix || ri < ix) return;
	if (le == ix && ix == ri) {
		// cout << "PRVAL " << le << ' ' << ri << ' ' << st[v] << '\n';
		st[v] *= m;
		st[v] /= d;
		// cout << "PVAL " << le << ' ' << ri << ' ' << st[v] << "; " << m << ' ' << d << '\n';
		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 -1;
	}
	if (0 != lzm[v] && 0 != lzd[v]) {
		// cout << "RELAX " << le << ' ' << ri << '\n';
		relax(v);
	}
	if (ql <= le && ri <= qr) {
		// cout << "VALUE " << le << ' ' << ri << ' ' << st[v] << '\n';
		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];
	}

	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 ++;
	// cout << "MUL " << val << ' ' << "DIV " << b[pos] << '\n';
	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 11 ms 33628 KB Output is correct
2 Correct 10 ms 33832 KB Output is correct
3 Correct 11 ms 33624 KB Output is correct
4 Correct 11 ms 33796 KB Output is correct
5 Correct 10 ms 33684 KB Output is correct
6 Correct 11 ms 33624 KB Output is correct
7 Correct 11 ms 33720 KB Output is correct
8 Correct 13 ms 33628 KB Output is correct
9 Correct 11 ms 33588 KB Output is correct
10 Correct 12 ms 33616 KB Output is correct
11 Correct 12 ms 33628 KB Output is correct
12 Correct 12 ms 33728 KB Output is correct
13 Correct 12 ms 33624 KB Output is correct
14 Correct 11 ms 33628 KB Output is correct
15 Correct 12 ms 33652 KB Output is correct
16 Correct 12 ms 33624 KB Output is correct
17 Correct 12 ms 33696 KB Output is correct
18 Correct 11 ms 33604 KB Output is correct
19 Correct 12 ms 33676 KB Output is correct
20 Correct 13 ms 33628 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 33628 KB Output is correct
2 Correct 12 ms 33792 KB Output is correct
3 Correct 14 ms 34008 KB Output is correct
4 Correct 12 ms 35676 KB Output is correct
5 Correct 12 ms 33628 KB Output is correct
6 Correct 12 ms 33736 KB Output is correct
7 Correct 12 ms 33628 KB Output is correct
8 Correct 12 ms 33628 KB Output is correct
9 Correct 13 ms 33628 KB Output is correct
10 Correct 12 ms 33624 KB Output is correct
11 Correct 12 ms 33628 KB Output is correct
12 Correct 12 ms 33760 KB Output is correct
13 Correct 13 ms 33732 KB Output is correct
14 Correct 12 ms 33700 KB Output is correct
15 Correct 12 ms 33616 KB Output is correct
16 Correct 12 ms 33880 KB Output is correct
17 Correct 12 ms 33628 KB Output is correct
18 Correct 12 ms 33628 KB Output is correct
19 Correct 11 ms 33732 KB Output is correct
20 Correct 11 ms 33664 KB Output is correct
21 Incorrect 11 ms 33800 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 33628 KB Output is correct
2 Correct 12 ms 33728 KB Output is correct
3 Correct 11 ms 33624 KB Output is correct
4 Correct 11 ms 33628 KB Output is correct
5 Correct 11 ms 33628 KB Output is correct
6 Correct 11 ms 33624 KB Output is correct
7 Correct 11 ms 33772 KB Output is correct
8 Correct 11 ms 33628 KB Output is correct
9 Correct 12 ms 33784 KB Output is correct
10 Correct 12 ms 33628 KB Output is correct
11 Correct 11 ms 33768 KB Output is correct
12 Correct 14 ms 33712 KB Output is correct
13 Correct 11 ms 33728 KB Output is correct
14 Correct 11 ms 33628 KB Output is correct
15 Correct 11 ms 33628 KB Output is correct
16 Correct 11 ms 33628 KB Output is correct
17 Correct 12 ms 33628 KB Output is correct
18 Correct 11 ms 33588 KB Output is correct
19 Correct 11 ms 33628 KB Output is correct
20 Correct 11 ms 33628 KB Output is correct
21 Incorrect 12 ms 33628 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 33628 KB Output is correct
2 Correct 10 ms 33700 KB Output is correct
3 Correct 11 ms 33628 KB Output is correct
4 Correct 11 ms 33628 KB Output is correct
5 Correct 12 ms 33628 KB Output is correct
6 Correct 10 ms 33664 KB Output is correct
7 Correct 11 ms 33628 KB Output is correct
8 Correct 11 ms 33776 KB Output is correct
9 Correct 12 ms 33628 KB Output is correct
10 Correct 11 ms 33596 KB Output is correct
11 Correct 11 ms 33624 KB Output is correct
12 Correct 12 ms 33684 KB Output is correct
13 Correct 14 ms 33628 KB Output is correct
14 Correct 12 ms 33628 KB Output is correct
15 Correct 10 ms 33764 KB Output is correct
16 Correct 15 ms 33636 KB Output is correct
17 Correct 12 ms 33624 KB Output is correct
18 Correct 13 ms 33592 KB Output is correct
19 Correct 11 ms 33628 KB Output is correct
20 Correct 12 ms 33628 KB Output is correct
21 Incorrect 12 ms 33812 KB Output isn't correct
22 Halted 0 ms 0 KB -