제출 #121039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
121039		khulegub	말 (IOI15_horses)	C++14	100 / 100	864 ms	60824 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<i64> st_mult;
vector<int> x, y;
int n;
void build_mult(int l, int r, int node){
	if(l == r){
		st_mult[node] = x[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build_mult(l, mid, ll(node));
	build_mult(mid + 1, r, rr(node));
	st_mult[node] = (st_mult[ll(node)] * st_mult[rr(node)]) % mod;
}
void update_mult(int pos, int l, int r, int node){
	if(l == r){
		st_mult[node] = x[l];
		return ;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) update_mult(pos, l, mid, ll(node));
	else update_mult(pos, mid + 1, r, rr(node));
	st_mult[node] = (st_mult[ll(node)] * st_mult[rr(node)]) % mod;
}
i64 query_mult(int ql, int qr, int l, int r, int node){
	if(qr < l || r < ql) return 1;
	if(ql <= l && r <= qr) return st_mult[node];
	int mid = (l + r) >> 1;
	return (query_mult(ql, qr, l, mid, ll(node)) * query_mult(ql, qr, mid + 1, r, rr(node))) % mod;
}	
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(r < pos || pos < l) return ;
	if(l == r){
		st_max[node] = l;
		return ;
	}
	int mid = (l + r) >> 1;
	update_max(pos, l, mid, ll(node));
	update_max(pos, 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);
	st_mult.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);
	build_mult(0, n-1, 0);
	// cout << query_max(0, n-1);
	int indx = query_max(0, n-1);
	return (query_mult(0, indx, 0, n-1, 0) * y[indx]) % mod;
}
int updateX(int pos, int val){
	x[pos] = val;
	update_inv(pos, 0, n-1, 0);
	// build_max(0, n-1, 0);
	update_max(pos, 0, n-1, 0);
	update_mult(pos, 0, n-1, 0);
	int indx = query_max(0, n-1);
	return (query_mult(0, indx, 0, n-1, 0) * y[indx]) % mod;
}
int updateY(int pos, int val){
	y[pos] = val;
	// build_max(0, n-1, 0);
	update_max(pos, 0, n-1, 0);
	int indx = query_max(0, n-1);
	return (query_mult(0, indx, 0, n-1, 0) * y[indx]) % mod;
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:141:52: warning: conversion to 'int' from 'i64 {aka long long int}' may alter its value [-Wconversion]
  return (query_mult(0, indx, 0, n-1, 0) * y[indx]) % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:150:52: warning: conversion to 'int' from 'i64 {aka long long int}' may alter its value [-Wconversion]
  return (query_mult(0, indx, 0, n-1, 0) * y[indx]) % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:157:52: warning: conversion to 'int' from 'i64 {aka long long int}' may alter its value [-Wconversion]
  return (query_mult(0, indx, 0, n-1, 0) * y[indx]) % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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