oj.uz

Submission #52686

# Submission time Handle Problem Language Result Execution time Memory
52686 2018-06-26T11:15:19 Z win11905 Horses (IOI15_horses) C++11
17 / 100
 445 ms 46340 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define long long long
using namespace std;

const int N = 1<<19, M = 1e9+7;

int n, X[N], Y[N];
double t[N<<1], lz[N<<1];
long val[N<<1], lzval[N<<1];

long powMod(long a, long b) {
	long ret = 1;
	while(b) {
		if(b & 1) ret = (ret * a) % M;
		a = (a * a) % M;
		b >>= 1;
	}
	return ret;
}

int invMod(long v) {
	return (int)powMod(v, M-2);
}

void update(int p) {
	if(t[p<<1] > t[p<<1|1]) val[p] = val[p<<1], t[p] = t[p<<1];
	else val[p] = val[p<<1|1], t[p] = t[p<<1|1];
}

void push(int p, int l, int r) {
	if(lzval[p] != 1 || lz[p] != 0.0) {
		val[p] = (val[p] * lzval[p]) % M;
		t[p] += lz[p];
		if(l != r) {
			lzval[p<<1] = (lzval[p<<1] * lzval[p]) % M;
			lzval[p<<1|1] = (lzval[p<<1|1] * lzval[p]) % M;
			lz[p<<1] += lz[p];
			lz[p<<1|1] += lz[p];
		}
	}	
	lzval[p] = 1, lz[p] = 0.0;
}

void build(int p = 1, int l = 0, int r = n-1) {
	if(l == r) {
		t[p] = log2(Y[l]);
		val[p] = Y[l];
		return;
	}
	int m = (l + r) >> 1;
	build(p<<1, l, m), build(p<<1|1, m+1, r);
	update(p);
}

template<typename T>
void travel(int x, int y, const T &f, int p = 1, int l = 0, int r = n-1) {
	push(p, l, r);
	if(x > r || l > y) return;
	if(x <= l && r <= y) return f(p, l, r);
	int m = (l + r) >> 1;
	travel(x, y, f, p<<1, l, m), travel(x, y, f, p<<1|1, m+1, r);
	update(p);	
}

void modify(int x, int y, int a, double b) {
	travel(x, y, [&](int p, int l, int r) {
		lz[p] += b;
		lzval[p] = (lzval[p] * a) % M;
		push(p, l, r);
	});
}

int init(int z, int x[], int y[]) {
	n = z;
	for(int i = 0; i < n; ++i) X[i] = x[i], Y[i] = y[i];
	fill(lzval, lzval + (::N<<1), 1);
	build();
	for(int i = 0; i < n; ++i) modify(i, n-1, X[i], log2(X[i]));
	return (int)val[1];
}

int updateX(int pos, int v) {	
	modify(pos, n-1, invMod(X[pos]), -log2(X[pos]));
	modify(pos, n-1, v, log2(v));
	return (int)val[1];
}

int updateY(int pos, int v) {
	modify(pos, pos, invMod(Y[pos]), -log2(Y[pos]));
	modify(pos, pos, v, log2(v));
	return (int)val[1];
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8568 KB Output is correct
2 Correct 8 ms 8668 KB Output is correct
3 Correct 7 ms 8800 KB Output is correct
4 Correct 7 ms 8880 KB Output is correct
5 Correct 8 ms 8944 KB Output is correct
6 Correct 8 ms 8944 KB Output is correct
7 Correct 7 ms 8944 KB Output is correct
8 Correct 8 ms 9060 KB Output is correct
9 Correct 7 ms 9060 KB Output is correct
10 Correct 7 ms 9060 KB Output is correct
11 Correct 8 ms 9060 KB Output is correct
12 Correct 7 ms 9060 KB Output is correct
13 Correct 8 ms 9060 KB Output is correct
14 Correct 7 ms 9060 KB Output is correct
15 Correct 7 ms 9060 KB Output is correct
16 Correct 8 ms 9060 KB Output is correct
17 Correct 8 ms 9060 KB Output is correct
18 Correct 7 ms 9060 KB Output is correct
19 Correct 8 ms 9060 KB Output is correct
20 Correct 8 ms 9060 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9060 KB Output is correct
2 Correct 8 ms 9060 KB Output is correct
3 Correct 8 ms 9060 KB Output is correct
4 Correct 9 ms 9060 KB Output is correct
5 Correct 8 ms 9060 KB Output is correct
6 Correct 9 ms 9060 KB Output is correct
7 Correct 8 ms 9060 KB Output is correct
8 Correct 8 ms 9060 KB Output is correct
9 Correct 7 ms 9060 KB Output is correct
10 Correct 8 ms 9060 KB Output is correct
11 Correct 8 ms 9060 KB Output is correct
12 Correct 7 ms 9060 KB Output is correct
13 Correct 8 ms 9060 KB Output is correct
14 Correct 8 ms 9060 KB Output is correct
15 Correct 9 ms 9064 KB Output is correct
16 Correct 10 ms 9068 KB Output is correct
17 Correct 9 ms 9072 KB Output is correct
18 Correct 8 ms 9076 KB Output is correct
19 Correct 7 ms 9080 KB Output is correct
20 Correct 8 ms 9084 KB Output is correct
21 Incorrect 8 ms 9088 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 23.0

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