Submission #71552

#	Time	Username	Problem	Language	Result	Execution time	Memory
71552		Sa1378	Horses (IOI15_horses)	C++17	100 / 100	979 ms	279360 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N ((int)501*1000)
#define MOD ((int)1e9+7)
int tavan(int x,int y){int res=1;while(y){res=1LL*res*((y%2)?x:1)%MOD;x=1LL*x*x%MOD;y/=2;}return res;}

int n,x[N],y[N];
set <int> s;
int segMul[4*N],segMax[4*N];

void updateMul(int q,int val,int xl=0,int xr=n,int id=1)
{
	if(xl==xr-1)
	{
		segMul[id]=val;
		return ;
	}
	int mid=(xl+xr)/2;
	if(q<mid)updateMul(q,val,xl,mid,id*2);
	else updateMul(q,val,mid,xr,id*2+1);
	segMul[id]=1LL*segMul[id*2]*segMul[id*2+1]%MOD;
	return ;
}

void updateMax(int q,int val,int xl=0,int xr=n,int id=1)
{
	if(xl==xr-1)
	{
		segMax[id]=val;
		return ;
	}
	int mid=(xl+xr)/2;
	if(q<mid)updateMax(q,val,xl,mid,id*2);
	else updateMax(q,val,mid,xr,id*2+1);
	segMax[id]=max(segMax[id*2],segMax[id*2+1]);
	return ;
}

int queryMul(int q,int xl=0,int xr=n,int id=1)
{
	if(xr<=q)return segMul[id];
	int mid=(xl+xr)/2,res=queryMul(q,xl,mid,id*2);
	if(mid<q)res=1LL*res*queryMul(q,mid,xr,id*2+1)%MOD;
	return res;
}

int queryMax(int q,int xl=0,int xr=n,int id=1)
{
	if(q<=xl)return segMax[id];
	int mid=(xl+xr)/2,res=queryMax(q,mid,xr,id*2+1);
	if(q<mid)res=max(res,queryMax(q,xl,mid,id*2));
	return res;
}

int solve()
{
	vector <int> vec;
	auto it=s.end();it--;
	ll now=1;
	while(1)
	{
		vec.push_back(*it);
		now*=x[*it];
		if(now>=1e9+10 || it==s.begin())break;
		it--;
	}
	reverse(vec.begin(),vec.end());
	now=1;
	ll ans=0;
	for(auto u:vec)
	{
		if(u!=vec[0])now*=x[u];
		ans=max(ans,now*queryMax(u));
	}
	ans%=MOD;
	ans*=queryMul(vec[0]+1);ans%=MOD;
	return ans;
}

int init(int n2, int X[], int Y[])
{
	n=n2;
	for(int i=0;i<n;i++)
	{
		x[i]=X[i];y[i]=Y[i];
		if(x[i]>1 || i==0)s.insert(i);
		updateMul(i,x[i]);
		updateMax(i,y[i]);
	}
	return solve();
}

int updateX(int pos, int val)
{	
	x[pos]=val;
	if(x[pos]==1 && pos>0)s.erase(pos);
	else s.insert(pos);
	updateMul(pos,x[pos]);
	return solve();
}

int updateY(int pos, int val)
{
	y[pos]=val;
	updateMax(pos,y[pos]);
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'int tavan(int, int)':
horses.cpp:7:66: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 int tavan(int x,int y){int res=1;while(y){res=1LL*res*((y%2)?x:1)%MOD;x=1LL*x*x%MOD;y/=2;}return res;}
                                                                  ^
horses.cpp:7:80: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 int tavan(int x,int y){int res=1;while(y){res=1LL*res*((y%2)?x:1)%MOD;x=1LL*x*x%MOD;y/=2;}return res;}
                                                                                ^
horses.cpp: In function 'void updateMul(int, int, int, int, int)':
horses.cpp:23:44: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  segMul[id]=1LL*segMul[id*2]*segMul[id*2+1]%MOD;
                                            ^
horses.cpp: In function 'int queryMul(int, int, int, int)':
horses.cpp:45:48: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  if(mid<q)res=1LL*res*queryMul(q,mid,xr,id*2+1)%MOD;
                                                ^
horses.cpp: In function 'int solve()':
horses.cpp:66:15: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
   if(now>=1e9+10 || it==s.begin())break;
               ^~
horses.cpp:79:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ans;
         ^~~

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