Submission #986370

#	Time	Username	Problem	Language	Result	Execution time	Memory
986370		Pyqe	Horses (IOI15_horses)	C++17	100 / 100	617 ms	72576 KiB

horses

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

using namespace std;

int n,ma=1e9,a[500069],wg[500069],fw[2][500069],fi,pwk,dv=1e9+7,inf=1e9;

struct segtree
{
	int l,r,mx;
	segtree *p[2];
	
	void bd(int lh,int rh)
	{
		l=lh;
		r=rh;
		if(l==r)
		{
			mx=wg[l];
		}
		else
		{
			int ii,md=(l+r)/2;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
			mx=max(p[0]->mx,p[1]->mx);
		}
	}
	void ud(int x,int w)
	{
		if(l>x||r<x);
		else if(l>=x&&r<=x)
		{
			mx=w;
		}
		else
		{
			int ii;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ud(x,w);
			}
			mx=max(p[0]->mx,p[1]->mx);
		}
	}
	int qr(int lh,int rh)
	{
		if(l>rh||r<lh)
		{
			return -inf;
		}
		else if(l>=lh&&r<=rh)
		{
			return mx;
		}
		else
		{
			return max(p[0]->qr(lh,rh),p[1]->qr(lh,rh));
		}
	}
}
sg;

int pw(int x,int y)
{
	if(!y)
	{
		return 1;
	}
	pwk=pw(x,y/2);
	pwk=(long long)pwk*pwk%dv;
	if(y%2)
	{
		pwk=(long long)pwk*x%dv;
	}
	return pwk;
}

void ud(int xx,int x,int w)
{
	for(fi=x;fi<=n;fi+=fi&-fi)
	{
		if(!xx)
		{
			fw[xx][fi]=(long long)fw[xx][fi]*w%dv;
		}
		else
		{
			fw[xx][fi]+=w;
		}
	}
}

int qr(int xx,int x)
{
	int z=!xx;
	
	for(fi=x;fi;fi-=fi&-fi)
	{
		if(!xx)
		{
			z=(long long)z*fw[xx][fi]%dv;
		}
		else
		{
			z+=fw[xx][fi];
		}
	}
	return z;
}

int bl(int xx,int x)
{
	int i,p=0,sm=0;
	
	for(i=18;i+1;i--)
	{
		if((p|1<<i)<=n&&sm+fw[xx][p|1<<i]<x)
		{
			p|=1<<i;
			sm+=fw[xx][p];
		}
	}
	return p;
}

int slv()
{
	int k,l;
	long long ml=1,mx=0;
	
	for(k=n+1;k&&ml<=ma;)
	{
		l=k;
		k=bl(1,qr(1,k-1))+1;
		if(k==l)
		{
			break;
		}
		mx=max(mx*a[l],(long long)sg.qr(k,l-1));
		ml*=a[k];
	}
	return mx%dv*qr(0,k)%dv;
}

int init(int on,int aa[],int wgg[])
{
	int i;
	
	n=on;
	for(i=1;i<=n;i++)
	{
		fw[0][i]=1;
	}
	for(i=1;i<=n;i++)
	{
		a[i]=aa[i-1];
		wg[i]=wgg[i-1];
		ud(0,i,a[i]);
		ud(1,i,!!(a[i]-1));
	}
	sg.bd(1,n);
	return slv();
}

int updateX(int x,int w)
{
	x++;
	ud(0,x,(long long)pw(a[x],dv-2)*w%dv);
	ud(1,x,!!(w-1)-!!(a[x]-1));
	a[x]=w;
	return slv();
}

int updateY(int x,int w)
{
	x++;
	sg.ud(x,w);
	return slv();
}

Compilation message (stderr)

horses.cpp: In function 'int pw(int, int)':
horses.cpp:76:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   76 |  pwk=(long long)pwk*pwk%dv;
      |      ~~~~~~~~~~~~~~~~~~^~~
horses.cpp:79:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |   pwk=(long long)pwk*x%dv;
      |       ~~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'void ud(int, int, int)':
horses.cpp:90:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |    fw[xx][fi]=(long long)fw[xx][fi]*w%dv;
      |               ~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int qr(int, int)':
horses.cpp:107:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  107 |    z=(long long)z*fw[xx][fi]%dv;
      |      ~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int slv()':
horses.cpp:148:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  148 |  return mx%dv*qr(0,k)%dv;
      |         ~~~~~~~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:174:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  174 |  ud(0,x,(long long)pw(a[x],dv-2)*w%dv);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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