Submission #302338

#	Time	Username	Problem	Language	Result	Execution time	Memory
302338		bensonlzl	Horses (IOI15_horses)	C++14	100 / 100	949 ms	95516 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-9;

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 (r < l) return 1;
		if (l > e || r < s) return 1;
		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 lastpos = n;
	ld bestLog = logl(Yroot->query(1,*(non1X.begin())-1));
	ll bestval = Yroot->query(1,*(non1X.begin())-1);
	auto it = (--non1X.end());
	//for (auto it2 : non1X) cerr << it2 << ' ';
	//cerr << '\n';
	for (int i = 0; i < 30; ++i){
		//cerr << bestLog << ' ' << bestval << '\n';
		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;
		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 (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);
	non1X.insert(1);
	return solve();
}

int updateX(int pos, int val) {	
	pos++;
	ll valc = (modinv(Xval[pos]) * (ll)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);
	non1X.insert(1);
	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:91:54: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   ld curLog = querylogX(pos) + logl(Yroot->query(pos,lastpos));
      |                                                      ^~~~~~~
horses.cpp:94:46: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   94 |    bestval = (queryX(pos) * Yroot->query(pos,lastpos)) % mod;
      |                                              ^~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:122:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  122 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:139:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  139 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:146:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  146 |  return solve();
      |         ~~~~~^~

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