oj.uz

Submission #613994

# Submission time Handle Problem Language Result Execution time Memory
613994 2022-07-30T15:54:00 Z Lucpp Horses (IOI15_horses) C++17
17 / 100
 720 ms 65396 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;

template<typename T>
struct SegTree{
	virtual T combine(T t1, T t2) = 0;
	virtual T id() = 0;

	int cap;
	vector<T> seg;
	void build(const vector<T>& v){
		int n = (int)v.size();
		for(cap=1; cap < n; cap*=2);
		seg.resize(2*cap, id());
		for(int i = 0; i < n; i++) seg[i+cap] = v[i];
		for(int i = cap-1; i >= 1; i--) seg[i] = combine(seg[2*i], seg[2*i+1]);
	}
	void upd(int i, T v){
		i += cap;
		seg[i] = v;
		while(i > 1){
			i /= 2;
			seg[i] = combine(seg[2*i], seg[2*i+1]);
		}
	}
	T qry(int l, int r, int a, int b, int i){
		if(l <= a && b <= r) return seg[i];
		if(b < l || r < a) return id();
		int m = (a+b)/2;
		return combine(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
	}
	T qry(int l, int r){return qry(l, r, 1, cap, 1);}
};

struct ProdTree : SegTree<ll> {
	ll combine(ll t1, ll t2) override {return (t1*t2)%MOD;}
	ll id() override {return 1;}
};
struct MaxTree : SegTree<ll> {
	ll combine(ll t1, ll t2) override {return max(t1, t2);}
	ll id() override {return 0;}
};

vector<ll> x, y;
set<int> non1;
int n;
ProdTree p;
MaxTree m;

int calc(){
	ll prod = 1;
	auto it = non1.rbegin();
	for(; it != non1.rend() && prod < MOD; it++){
		prod *= x[*it];
	}
	int last = prod<MOD ? -1 : *it;
	ll pref = p.qry(1, last+1);
	prod = 1;
	ll best = 0;
	while(it != non1.rbegin()){
		it--;
		best = max(best, prod*m.qry(last+1, *it));
		prod *= x[*it];
		last = *it;
	}
	best = max(best, prod*m.qry(last+1, n));
	return int(((best%MOD)*pref)%MOD);
}

int init(int N, int X[], int Y[]){
	n = N;
	x.resize(n);
	y.resize(n);
	for(int i = 0; i < n; i++){
		x[i] = X[i], y[i] = Y[i];
		if(x[i] != 1) non1.insert(i);
	}
	p.build(x);
	m.build(y);
	return calc();
}

int updateX(int pos, int val) {
	x[pos] = val;
	p.upd(pos, val);
	if(val == 1) non1.erase(pos);
	else non1.insert(pos);
	return calc();
}

int updateY(int pos, int val) {
	y[pos] = val;
	m.upd(pos, val);
	return calc();
}

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 52880 KB Output is correct
2 Incorrect 333 ms 65396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 300 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Incorrect 0 ms 304 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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