Submission #302293

#	Time	Username	Problem	Language	Result	Execution time	Memory
302293		bensonlzl	Horses (IOI15_horses)	C++14	0 / 100	1549 ms	95248 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const ll mod = 1000000007ll;
const ld eps = 1e-7;

ll modinv(ll x){
	ll ans = 1, base = x, exp = mod-2;
	while (exp){
		if (exp & 1) ans *= base;
		base *= base;
		base %= mod;
		ans %= mod;
	}
	return ans;
}

ll Xval[500005], Yval[500005];
ll Xprod[500005];
ld logX[500005];
int n;

struct node{
	node *left = nullptr, *right = nullptr;
	int s, e;
	ll maxi = 0;
	node(int _s, int _e){
		s = _s;
		e = _e;
		if (s == e){
			maxi = Yval[s];
			return;
		}
		left = new node(s,(s+e)/2);
		right = new node((s+e)/2+1,e);
		maxi = max(left->maxi,right->maxi);
	}
	void update(int x){
		if (s == e){
			maxi = Yval[s];
			return;
		}
		if (x <= (s+e)/2) left->update(x);
		else right->update(x);
		maxi = max(left->maxi,right->maxi);
	}
	ll query(int l, int r){
		if (l > e || r < s) return -1e9;
		else if (l <= s && e <= r) return maxi;
		return max(left->query(l,r),right->query(l,r));
	}
} *Yroot = nullptr;

set<int> non1X;


ld querylogX(int x){
	ld sum = 0;
	for (; x; x -= (x & -x)) sum += logX[x];
	return sum;
}

ll queryX(int x){
	ll prod = 1;
	for (; x; x -= (x & -x)){
		prod *= Xprod[x];
		prod %= mod;
	}
	return prod;
}

ll solve(){
	//cerr << "SOLVING\n";
	if (non1X.empty()) return Yroot->query(1,n);
	ll run = 1, lastpos = n;
	ld bestLog = 1;
	ll bestval = 0;
	auto it = non1X.end();
	if (it == non1X.begin()) return 1;
	it--;
	while (run <= 1e9){
		
		int pos = *it;
		
		ld curLog = querylogX(pos) + logl(Yroot->query(pos,lastpos));
		//cerr << pos << ' ' << lastpos << '\n';
		//cerr << querylogX(pos) << ' ' << logl(Yroot->query(pos,lastpos)) << '\n';
		
		//cerr << pos << ' ' << curLog << '\n';
		if (curLog > bestLog + eps){
			bestLog = curLog;
			bestval = (queryX(pos) * Yroot->query(pos,lastpos)) % mod;
		}
		
		lastpos = pos-1;
		
		run *= Xval[pos];
		if (it == non1X.begin()) break;
		else *it--;
	}
	//cerr << bestval << '\n';
	//cerr << "END SOLVING\n";
	return bestval;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 1; i <= n; ++i){
		Xprod[i] = Xval[i] = X[i-1];
		Yval[i] = Y[i-1];
		logX[i] = logl(X[i-1]);
		if (X[i] != 1) non1X.insert(i);
	}
	for (int i = 1; i < 20; ++i){
		for (int j = (1 << i); j <= n; j += (1 << i)){
			Xprod[j] *= Xprod[j - (1 << (i-1))];
			Xprod[j] %= mod;
			logX[j] += logX[j - (1 << (i-1))];
		}
	}
	Yroot = new node(1,N);
	return solve();
}

int updateX(int pos, int val) {	
	pos++;
	ll valc = (modinv(Xval[pos]) * val)%mod;
	ld lg1 = logl(Xval[pos]), lg2 = logl(val);
	int x = pos;
	for (; x <= n; x += (x & -x)){
		Xprod[x] *= valc;
		Xprod[x] %= mod;
		logX[x] += lg2 - lg1;
	}
	if (Xval[pos] == 1 && val != 1) non1X.insert(pos);
	else if (Xval[pos] != 1 && val == 1) non1X.erase(pos);
	Xval[pos] = val; 
	return solve();
}

int updateY(int pos, int val) {
	pos++;
	Yval[pos] = val;
	Yroot->update(pos);
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'll solve()':
horses.cpp:86:9: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
   86 |  while (run <= 1e9){
      |         ^~~
horses.cpp:90:54: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   90 |   ld curLog = querylogX(pos) + logl(Yroot->query(pos,lastpos));
      |                                                      ^~~~~~~
horses.cpp:97:46: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   97 |    bestval = (queryX(pos) * Yroot->query(pos,lastpos)) % mod;
      |                                              ^~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:127:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  127 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:143:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  143 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:150:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  150 |  return solve();
      |         ~~~~~^~

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