oj.uz

Submission #588222

# Submission time Handle Problem Language Result Execution time Memory
588222 2022-07-02T20:13:10 Z dnass Horses (IOI15_horses) C++17
100 / 100
 1205 ms 73604 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(){
	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);
	big.insert(0);
	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 if(pos!=0){
		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 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 252 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 0 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 1 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
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 1 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 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 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 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 7 ms 340 KB Output is correct
24 Correct 8 ms 340 KB Output is correct
25 Correct 7 ms 424 KB Output is correct
26 Correct 7 ms 340 KB Output is correct
27 Correct 9 ms 384 KB Output is correct
28 Correct 8 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 9 ms 448 KB Output is correct
31 Correct 6 ms 388 KB Output is correct
32 Correct 7 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1144 ms 61032 KB Output is correct
2 Correct 1095 ms 61312 KB Output is correct
3 Correct 1190 ms 61288 KB Output is correct
4 Correct 1155 ms 61220 KB Output is correct

Subtask #4
23.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 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 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 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 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 Correct 0 ms 212 KB Output is correct
23 Correct 7 ms 340 KB Output is correct
24 Correct 7 ms 380 KB Output is correct
25 Correct 9 ms 340 KB Output is correct
26 Correct 7 ms 340 KB Output is correct
27 Correct 10 ms 340 KB Output is correct
28 Correct 9 ms 340 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 9 ms 440 KB Output is correct
31 Correct 5 ms 340 KB Output is correct
32 Correct 8 ms 392 KB Output is correct
33 Correct 162 ms 40824 KB Output is correct
34 Correct 139 ms 40800 KB Output is correct
35 Correct 289 ms 71044 KB Output is correct
36 Correct 281 ms 71064 KB Output is correct
37 Correct 158 ms 38896 KB Output is correct
38 Correct 201 ms 51720 KB Output is correct
39 Correct 48 ms 38788 KB Output is correct
40 Correct 266 ms 66260 KB Output is correct
41 Correct 120 ms 38716 KB Output is correct
42 Correct 129 ms 38860 KB Output is correct
43 Correct 174 ms 66472 KB Output is correct
44 Correct 183 ms 66636 KB Output is correct

Subtask #5
23.0 / 23.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 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 1 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 1 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 340 KB Output is correct
24 Correct 7 ms 380 KB Output is correct
25 Correct 7 ms 340 KB Output is correct
26 Correct 6 ms 340 KB Output is correct
27 Correct 8 ms 340 KB Output is correct
28 Correct 7 ms 444 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 9 ms 448 KB Output is correct
31 Correct 6 ms 340 KB Output is correct
32 Correct 8 ms 400 KB Output is correct
33 Correct 1125 ms 64988 KB Output is correct
34 Correct 1051 ms 73604 KB Output is correct
35 Correct 1205 ms 64940 KB Output is correct
36 Correct 1202 ms 68724 KB Output is correct
37 Correct 152 ms 40780 KB Output is correct
38 Correct 133 ms 40760 KB Output is correct
39 Correct 302 ms 71076 KB Output is correct
40 Correct 295 ms 70996 KB Output is correct
41 Correct 158 ms 38988 KB Output is correct
42 Correct 188 ms 51732 KB Output is correct
43 Correct 48 ms 38688 KB Output is correct
44 Correct 275 ms 66152 KB Output is correct
45 Correct 104 ms 38840 KB Output is correct
46 Correct 133 ms 38844 KB Output is correct
47 Correct 195 ms 66484 KB Output is correct
48 Correct 212 ms 66684 KB Output is correct
49 Correct 1031 ms 43768 KB Output is correct
50 Correct 945 ms 43780 KB Output is correct
51 Correct 1090 ms 72956 KB Output is correct
52 Correct 1028 ms 72540 KB Output is correct
53 Correct 1088 ms 42164 KB Output is correct
54 Correct 1012 ms 55748 KB Output is correct
55 Correct 163 ms 39764 KB Output is correct
56 Correct 1165 ms 67924 KB Output is correct
57 Correct 700 ms 40464 KB Output is correct
58 Correct 972 ms 41148 KB Output is correct
59 Correct 194 ms 66540 KB Output is correct