Submission #302312

#	Time	Username	Problem	Language	Result	Execution time	Memory
302312		bensonlzl	Horses (IOI15_horses)	C++14	37 / 100	1139 ms	95432 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;
		exp >>= 1;
	}
	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 <= 1e10){
		int pos = *it;
		ld curLog = querylogX(pos) + logl(Yroot->query(pos,lastpos));
		if (curLog > bestLog + eps){
			bestLog = curLog;
			bestval = (queryX(pos) * Yroot->query(pos,lastpos)) % mod;
		}
		lastpos = pos-1;
		run *= Xval[pos];
		assert(Xval[pos] != 1);
		if (it == non1X.begin()) break;
		else it--;
	}
	if (lastpos != 0){
		ld curLog = querylogX(1) + logl(Yroot->query(1,lastpos));
		if (curLog > bestLog + eps){
			bestLog = curLog;
			bestval = (queryX(1) * Yroot->query(1,lastpos)) % mod;
		}
	}
	
	//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 (Xval[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:87:9: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
   87 |  while (run <= 1e10){
      |         ^~~
horses.cpp:89:54: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   89 |   ld curLog = querylogX(pos) + logl(Yroot->query(pos,lastpos));
      |                                                      ^~~~~~~
horses.cpp:92:46: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   92 |    bestval = (queryX(pos) * Yroot->query(pos,lastpos)) % mod;
      |                                              ^~~~~~~
horses.cpp:101:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  101 |   ld curLog = querylogX(1) + logl(Yroot->query(1,lastpos));
      |                                                  ^~~~~~~
horses.cpp:104:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  104 |    bestval = (queryX(1) * Yroot->query(1,lastpos)) % mod;
      |                                          ^~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:129:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  129 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:145:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  145 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:152:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  152 |  return solve();
      |         ~~~~~^~

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