Submission #120839

#	Time	Username	Problem	Language	Result	Execution time	Memory
120839		khulegub	Horses (IOI15_horses)	C++14	17 / 100	128 ms	33416 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, )
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;
}
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()
	return 0;
}
int updateY(int pos, int val){
	return 0;
}

Compilation message (stderr)

horses.cpp: In function 'int updateX(int, int)':
horses.cpp:98:17: warning: unused parameter 'pos' [-Wunused-parameter]
 int updateX(int pos, int val){
                 ^~~
horses.cpp:98:26: warning: unused parameter 'val' [-Wunused-parameter]
 int updateX(int pos, int val){
                          ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:103:17: warning: unused parameter 'pos' [-Wunused-parameter]
 int updateY(int pos, int val){
                 ^~~
horses.cpp:103:26: warning: unused parameter 'val' [-Wunused-parameter]
 int updateY(int pos, int val){
                          ^~~

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