oj.uz

Submission #588221

# Submission time Handle Problem Language Result Execution time Memory
588221 2022-07-02T20:03:56 Z dnass Horses (IOI15_horses) C++17
37 / 100
 1186 ms 73616 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef long double lf;
#define MOD 1000000007LL
#define INF 1000000000000000000LL

lld n;
vector<lld> x, y;
set<lld> big;

struct itemX{
	lld val;
	itemX(){
		val = 0;
	}
	itemX(lld valval){
		val=valval;
		val%=MOD;
	}
};

itemX merge(itemX a, itemX b){
	lld res = a.val*b.val; res%=MOD;
	return itemX(res);
}

itemX build_leaf(lld xxx){
	return itemX(xxx);
}

itemX X_NEUT = itemX(1);

struct STX{

	vector<itemX> st;

	void init(){
		lld sz = 1;
		while(sz<n) sz*=2;
		st.resize(2*sz);
	}

	void build(lld v = 1, lld tl = 0, lld tr = n-1){
		if(tl==tr) st[v] = build_leaf(x[tl]);
		else{
			lld tm = (tl+tr)/2;
			build(2*v, tl, tm);
			build(2*v+1,tm+1,tr);
			st[v] = merge(st[2*v], st[2*v+1]);
		}
	}

	itemX query(lld l, lld r, lld v = 1, lld tl=0, lld tr=n-1){
		if(l>r) return X_NEUT;
		if(l==tl&&r==tr) return st[v];
		lld tm = (tl+tr)/2;
		return merge(query(l,min(r,tm),2*v, tl, tm),query(max(l, tm+1), r, 2*v+1, tm+1,tr));
	}

	void upd(lld new_val, lld pos, lld v=1,lld tl=0, lld tr=n-1){
		if(tl==tr) st[v] = build_leaf(new_val);
		else{
			lld tm = (tl+tr)/2;
			if(pos<=tm) upd(new_val, pos, 2*v, tl, tm);
			else upd(new_val, pos, 2*v+1,tm+1,tr);
			st[v] = merge(st[2*v],st[2*v+1]);
		}
	}

};

struct itemY{
	lld val, ind;
	itemY(){
		val=-INF;
		ind = -1;
	}
	itemY(lld valval, lld indind){
		val=valval, ind=indind;
	}
};

itemY merge(itemY a, itemY b){
	return a.val>b.val?a:b;
}

itemY build_leaf(lld xxx, lld indind){
	return itemY(xxx,indind);
}

itemY Y_NEUT = itemY(-INF,-1);

struct STY{

	vector<itemY> st;

	void init(){
		lld sz = 1;
		while(sz<n) sz*=2;
		st.resize(2*sz);
	}

	void build(lld v = 1, lld tl = 0, lld tr = n-1){
		if(tl==tr) st[v] = build_leaf(y[tl], tl);
		else{
			lld tm = (tl+tr)/2;
			build(2*v, tl, tm);
			build(2*v+1,tm+1,tr);
			st[v] = merge(st[2*v], st[2*v+1]);
		}
	}

	itemY query(lld l, lld r, lld v = 1, lld tl=0, lld tr=n-1){
		if(l>r) return Y_NEUT;
		if(l==tl&&r==tr) return st[v];
		lld tm = (tl+tr)/2;
		return merge(query(l,min(r,tm),2*v, tl, tm),query(max(l, tm+1), r, 2*v+1, tm+1,tr));
	}

	void upd(lld new_val, lld pos, lld v=1,lld tl=0, lld tr=n-1){
		if(tl==tr) st[v] = build_leaf(new_val, tl);
		else{
			lld tm = (tl+tr)/2;
			if(pos<=tm) upd(new_val, pos, 2*v, tl, tm);
			else upd(new_val, pos, 2*v+1,tm+1,tr);
			st[v] = merge(st[2*v],st[2*v+1]);
		}
	}

};

STX segx;
STY segy;

int calc(){
	if(big.empty()){
		return (int)segy.query(0,n-1).val;
	}
	auto it = big.end();
	for(int i=0;i<31;i++){
		if(it==big.begin()) break;
		--it;
	}
	auto it2 = it; ++it2;
	lld next_pos = it2==big.end()?n:(*it2);
	itemY mxY = segy.query((*it), next_pos-1);
	lf cur = log((lf)x[(*it)])+log((lf)mxY.val);
	lf mx = cur;
	lld mx_pos = mxY.ind;
	lld prevY = mxY.ind;
	++it;
	while(it!=big.end()){
		cur -= log((lf)y[prevY]);
		it2 = it; ++it2;
		next_pos = it2==big.end()?n:(*it2);
		mxY = segy.query((*it), next_pos-1);
		cur += log((lf)x[(*it)])+log((lf)mxY.val);
		if(cur>mx){
			mx = cur;
			mx_pos = mxY.ind;
		}
		prevY = mxY.ind;
		++it;
	}
	lld res = segx.query(0, mx_pos).val;
	res *= y[mx_pos]; res%=MOD;
	return (int)res;
}

int init(int N, int X[], int Y[]) {
	n = (lld) N;
	x.resize(n); y.resize(n);
	for(lld i=0;i<n;i++){
		x[i] = (lld)X[i]; y[i] = (lld)Y[i];
		if(x[i]>1) big.insert(i);
	}
	segx.init(); segx.build();
	segy.init(); segy.build();
	return calc();
}

int updateX(int pos, int val){
	segx.upd(val, pos);
	x[pos] = val;
	if(val>1){
		big.insert(pos);
	}else{
		auto it = big.find(pos);
		if(it!=big.end()) big.erase(it);
	}
	return calc();
}

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 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 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 228 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 0 ms 300 KB Output is correct
19 Correct 0 ms 304 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 1 ms 304 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 300 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 7 ms 404 KB Output is correct
24 Correct 7 ms 340 KB Output is correct
25 Correct 7 ms 444 KB Output is correct
26 Correct 7 ms 340 KB Output is correct
27 Incorrect 7 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1117 ms 64916 KB Output is correct
2 Correct 1143 ms 73616 KB Output is correct
3 Correct 1186 ms 64944 KB Output is correct
4 Correct 1179 ms 68804 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 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 1 ms 300 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 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 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 1 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 1 ms 300 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 304 KB Output is correct
23 Correct 8 ms 340 KB Output is correct
24 Correct 7 ms 316 KB Output is correct
25 Correct 7 ms 440 KB Output is correct
26 Correct 7 ms 464 KB Output is correct
27 Incorrect 8 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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