제출 #120847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
120847		khulegub	말 (IOI15_horses)	C++14	17 / 100	1555 ms	31736 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
#define ll(x) x*2+1
#define rr(x) x*2+2
#define eps 1e-9
using namespace std;
typedef long long i64;
int mod = 1e9 + 7;

// vector<i64> st;

vector<double> st_inv;
vector<int> st_max;
vector<int> x, y;
int n;
void build_inv(int l, int r, int node){
	if(l == r){
		st_inv[node] = 1.0 / ((double) x[l]);
		return ;
	}
	int mid = (l + r) >> 1;
	build_inv(l, mid, ll(node));
	build_inv(mid + 1, r, rr(node));
	st_inv[node] = st_inv[ll(node)] * st_inv[rr(node)];
}
void update_inv(int pos, int l, int r, int node){
	if(l == r){
		st_inv[node] = 1.0 / ((double) x[l]);
		return ;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) update_inv(pos, l, mid, ll(node));
	else update_inv(pos, mid + 1, r, rr(node));
	st_inv[node] = st_inv[ll(node)] * st_inv[rr(node)];
}
double query_inv(int ql, int qr, int l, int r, int node){
	if(qr < l || r < ql) return 1.0;
	if(ql <= l && r <= qr) return st_inv[node];
	int mid = (l + r) >> 1;
	return query_inv(ql, qr, l, mid, ll(node)) * query_inv(ql, qr, mid + 1, r, rr(node));
}
double query_inv(int ql, int qr){
	return query_inv(ql, qr, 0, n - 1, 0);
}
void build_max(int l, int r, int node){
	if(l == r){
		st_max[node] = l;
		return ;
	}
	int mid = (l + r) >> 1;
	build_max(l, mid, ll(node));
	build_max(mid + 1, r, rr(node));
	int li = st_max[ll(node)], ri = st_max[rr(node)];
	double inv = query_inv(li + 1, ri);
	double haritsa = ((double) y[ri]) / ((double) y[li]);
	if(haritsa > inv) st_max[node] = ri;
	else st_max[node] = li;
}
// void update_max(int pos, int l, int r, int node){
// 	if(pos < l || r < pos) return ;
// 	if(l == r){
// 		st_max[node] = l;
// 		return ;
// 	}
// 	int mid = (l + r) >> 1;
// 	update_max(l, mid, ll(node));
// 	update_max(mid + 1, r, rr(node));
// 	int li = st_max[ll(node)], ri = st_max[rr(node)];
// 	double inv = query_inv(li + 1, ri);
// 	double haritsa = ((double) y[ri]) / ((double) y[li]);
// 	if(haritsa >= inv) st_max[node] = ri;
// 	else st_max[node] = li;
// }
int query_max(int ql, int qr, int l, int r, int node){
	if(qr < l || r < ql) return -1;
	if(ql <= l && r <= qr) return st_max[node];
	int mid = (l + r) >> 1;
	int li = query_max(ql, qr, l, mid, ll(node));
	int ri = query_max(ql, qr, mid + 1, r, rr(node));
	if(li == -1){
		return ri;
	}
	else if(ri == -1){
		return li;
	}
	else{
		double inv = query_inv(li + 1, ri);
		double haritsa = ((double) y[ri]) / ((double) y[li]);
		if(haritsa > inv) return ri;
		else return li;
	}
}
int query_max(int ql, int qr){
	return query_max(ql, qr, 0, n-1, 0);
}
// void update()

int init(int N, int X[], int Y[]){
	n = N;
	x.resize(n);
	y.resize(n);
	st_inv.resize(4*n);
	st_max.resize(4*n);
	for(int i = 0; i < n; i++){
		x[i] = X[i];
		y[i] = Y[i];
	}
	build_inv(0, n-1, 0);
	build_max(0, n-1, 0);
	// cout << query_max(0, n-1);
	int indx = query_max(0, n-1);
	int ret = 1;
	for(int i = 0; i <= indx; i++){
		ret *= x[i];
		ret %= mod;
	}
	ret *= y[indx];
	ret %= mod;
	return ret;
}
int updateX(int pos, int val){
	x[pos] = val;
	update_inv(pos, 0, n-1, 0);
	build_max(0, n-1, 0);
	int indx = query_max(0, n-1);
	int ret = 1;
	for(int i = 0; i <= indx; i++){
		ret *= x[i];
		ret %= mod;
	}
	ret *= y[indx];
	ret %= mod;
	return ret;
}
int updateY(int pos, int val){
	y[pos] = val;
	build_max(0, n-1, 0);
	int indx = query_max(0, n-1);
	int ret = 1;
	for(int i = 0; i <= indx; i++){
		ret *= x[i];
		ret %= mod;
	}
	ret *= y[indx];
	ret %= mod;
	return ret;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23