Submission #609267

#	Time	Username	Problem	Language	Result	Execution time	Memory
609267		MrDeboo	Horses (IOI15_horses)	C++17	100 / 100	823 ms	68976 KiB

horses

#include "horses.h"
#include "bits/stdc++.h"
using namespace std;
long long multpl[2000000];
long long maxi[2000000];
long long X[500000];
set<int>st;
int n,N,L,R;
long long multp(int l=1,int r=N,int in=1){
	if(l>R||r<L)return 1;
	if(l>=L&&r<=R)return multpl[in];
	int mid=(l+r)/2;
	return (multp(l,mid,in*2)*multp(mid+1,r,in*2+1))%1000000007;
}
long long mx(int l=1,int r=N,int in=1){
	if(l>R||r<L)return 0;
	if(l>=L&&r<=R)return maxi[in];
	int mid=(l+r)/2;
	return max(mx(l,mid,in*2),mx(mid+1,r,in*2+1));
}

int slv(){
	deque<int>v;
	int g=31;
	auto it=st.end();
	while(it!=st.begin()&&g--){
		it--;
		v.push_back(*it);
	}
	sort(v.begin(),v.end());
	if(v.empty()||v[0]!=0)v.push_front(0);
	long long ans=0,in=0;
	long double LNGDB=0,f=1,a;
	for(int i=0;i<v.size();i++){
		f*=X[v[i]];
		L=v[i]+1;
		R=n;
		a=f*mx();
		if(a>LNGDB){
			LNGDB=a;
			in=v[i];
		}
	}
	L=1;
	R=in+1;
	ans=multp();
	L=in+1;
	R=n;
	ans*=mx();
	return ans%1000000007;
}

int init(int nn, int x[], int y[]) {
	n=nn;
	N=exp2(ceil(log2(n)));
	for(auto &i:multpl)i=1;
	for(int i=0;i<n;i++){
		if(x[i]!=1)st.insert(i);
		X[i]=x[i];
	}
	for(int i=0;i<n;i++)multpl[i+N]=x[i];
	for(int i=N-1;i;i--)multpl[i]=(multpl[i*2]*multpl[i*2+1])%1000000007;
	for(int i=0;i<n;i++)maxi[i+N]=y[i];
	for(int i=N-1;i;i--)maxi[i]=max(maxi[i*2],maxi[i*2+1]);
	return slv();
}


int updateX(int pos, int val) {
	if(X[pos]!=1)st.erase(pos);
	X[pos]=val;
	if(val!=1)st.insert(pos);
	int in=pos+N;
	multpl[in]=val;
	in/=2;
	while(in){
		multpl[in]=(multpl[in*2]*multpl[in*2+1])%1000000007;
		in/=2;
	}
	return slv();
}

int updateY(int pos, int val) {
	int in=pos+N;
	maxi[in]=val;
	in/=2;
	while(in){
		maxi[in]=max(maxi[in*2],maxi[in*2+1]);
		in/=2;
	}
	return slv();
}

Compilation message (stderr)

horses.cpp: In function 'int slv()':
horses.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
horses.cpp:45:6: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   45 |  R=in+1;
      |    ~~^~
horses.cpp:47:6: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   47 |  L=in+1;
      |    ~~^~
horses.cpp:50:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   50 |  return ans%1000000007;
      |         ~~~^~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:55:8: warning: conversion from 'double' to 'int' may change value [-Wfloat-conversion]
   55 |  N=exp2(ceil(log2(n)));
      |    ~~~~^~~~~~~~~~~~~~~

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