Submission #87983

#	Time	Username	Problem	Language	Result	Execution time	Memory
87983		Pajaraja	Horses (IOI15_horses)	C++17	100 / 100	1167 ms	91740 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define MOD 1000000007
long long y[500040],x[500040],pr,seg[2][2000040],pb[32],td;
void upd(int l,int r,int val,int k,int poz,int ind)
{
	if(l==r)
	{
		seg[k][ind]=val;
		return;
	}
	int s=(l+r)/2;
	if(s>=poz) upd(l,s,val,k,poz,2*ind);
	else upd(s+1,r,val,k,poz,2*ind+1);
	seg[k][ind]=fmax(seg[k][2*ind],seg[k][2*ind+1]);
}
long long find(int lt,int rt,int l,int r,int k,int ind)
{
	if(l>rt||r<lt) return 0;
	if(l>=lt&&r<=rt) return seg[k][ind];
	int s=(l+r)/2;
	return fmax(find(lt,rt,l,s,k,2*ind),find(lt,rt,s+1,r,k,2*ind+1));
}
long long mmi(long long b,int exp)
{
	if(exp==0) return 1;
	long long r=mmi(b,exp/2);
	r=(r*r)%MOD;
	if(exp%2==0) return r;
	return (r*b)%MOD;
}
int n,cnt;
int resi()
{
	bool gdd=false;
	if(cnt<32) 
	{
	    pb[cnt]=-1;
	    gdd=true;
	    cnt++;
	}
	long long prt=1;
	int ind=0,prev=n;
	for(int i=0;i<cnt;i++)
	{
		long long r=find(pb[i],prev-1,0,n-1,1,1);
		if(r>prt)
		{
		    prt=r;
		    ind=i;
		}
		if(pb[i]!=-1) prt*=x[pb[i]];
		prev=pb[i];
		if(prt>MOD) break;
	}
	prt=1;
	for(int i=0;i<ind;i++) if(pb[i]!=-1) prt*=x[pb[i]];
	prev=(ind==0?n:pb[ind-1]);
	long long r=find(pb[ind],prev-1,0,n-1,1,1);
	if(gdd) cnt--;
	return (((pr*mmi(prt,MOD-2))%MOD)*r)%MOD;
}
int init(int N, int X[], int Y[]) 
{
	n=N;
	pr=1;
	td=0;
	for(int i=0;i<n;i++)
	{
	    x[i]=X[i];
	    upd(0,n-1,x[i],0,i,1);
	}
	for(int i=0;i<n;i++) 
	{
	    y[i]=Y[i];
	    upd(0,n-1,y[i],1,i,1);
	}
	for(int i=0;i<n;i++) pr=(pr*x[i])%MOD;
	for(int i=n-1;i>=0;i--) if(x[i]>1)
	{
		pb[cnt]=i;
		cnt++;
		if(cnt==32) break;
	}
	for(int i=n-1;i>=0;i--) if(x[i]>1) td++;
	return resi();
}
int binarna(int l,int r,int k)
{
	if(l==r) return l;
	int s=(l+r+1)/2;
	if(find(s,k,0,n-1,0,1)>1) return binarna(s,r,k);
	return binarna(l,s-1,k);
}
int updateX(int pos, int val) 
{
	pr=(pr*mmi(x[pos],MOD-2))%MOD;
	long long tmp,r=x[pos];
	x[pos]=val;
	pr=(pr*val)%MOD;
	upd(0,n-1,val,0,pos,1);
	if(r==1 && val>1)
	{
		td++;
		int d=33,prev=n;
		for(int i=0;i<cnt;i++)
		{
			if(pos>pb[i] && pos<prev)
			{
				d=i;
				break;
			}
			prev=pb[i];
		}
		for(int i=31;i>d;i--) pb[i]=pb[i-1];
		if(d==33&&cnt<32) pb[cnt]=pos;
		pb[d]=pos;
		cnt=fmin(32,td);
	}
	if(r>1&&val==1)
	{
		td--;
		int d=33;
		for(int i=0;i<cnt;i++)
		{
			if(pb[i]==pos)
			{
				d=i;
				break;
			}
		}
		for(int i=d;i<cnt-1;i++) pb[i]=pb[i+1];
		if(td>=32&&d!=33) pb[31]=binarna(0,pb[30]-1,pb[30]-1);
		cnt=fmin(32,td);
	}
	return resi();
}
int updateY(int pos, int val) 
{
	upd(0,n-1,val,1,pos,1);
	return resi();
}
//QED

Compilation message (stderr)

horses.cpp: In function 'void upd(int, int, int, int, int, int)':
horses.cpp:15:31: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
  seg[k][ind]=fmax(seg[k][2*ind],seg[k][2*ind+1]);
                   ~~~~~~~~~~~~^
horses.cpp:15:47: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
  seg[k][ind]=fmax(seg[k][2*ind],seg[k][2*ind+1]);
                                 ~~~~~~~~~~~~~~^
horses.cpp:15:18: warning: conversion to 'long long int' from 'double' may alter its value [-Wfloat-conversion]
  seg[k][ind]=fmax(seg[k][2*ind],seg[k][2*ind+1]);
              ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'long long int find(int, int, int, int, int, int)':
horses.cpp:22:18: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
  return fmax(find(lt,rt,l,s,k,2*ind),find(lt,rt,s+1,r,k,2*ind+1));
              ~~~~^~~~~~~~~~~~~~~~~~~
horses.cpp:22:42: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
  return fmax(find(lt,rt,l,s,k,2*ind),find(lt,rt,s+1,r,k,2*ind+1));
                                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:22:13: warning: conversion to 'long long int' from 'double' may alter its value [-Wfloat-conversion]
  return fmax(find(lt,rt,l,s,k,2*ind),find(lt,rt,s+1,r,k,2*ind+1));
         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int resi()':
horses.cpp:46:24: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   long long r=find(pb[i],prev-1,0,n-1,1,1);
                    ~~~~^
horses.cpp:53:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   prev=pb[i];
        ~~~~^
horses.cpp:58:14: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  prev=(ind==0?n:pb[ind-1]);
       ~~~~~~~^~~~~~~~~~~~~
horses.cpp:59:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  long long r=find(pb[ind],prev-1,0,n-1,1,1);
                   ~~~~~~^
horses.cpp:61:38: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (((pr*mmi(prt,MOD-2))%MOD)*r)%MOD;
                                      ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:71:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
      upd(0,n-1,x[i],0,i,1);
                ~~~^
horses.cpp:76:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
      upd(0,n-1,y[i],1,i,1);
                ~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:113:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    prev=pb[i];
         ~~~~^
horses.cpp:118:17: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
   cnt=fmin(32,td);
                 ^
horses.cpp:118:11: warning: conversion to 'int' from 'double' may alter its value [-Wfloat-conversion]
   cnt=fmin(32,td);
       ~~~~^~~~~~~
horses.cpp:133:44: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   if(td>=32&&d!=33) pb[31]=binarna(0,pb[30]-1,pb[30]-1);
                                      ~~~~~~^~
horses.cpp:133:53: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   if(td>=32&&d!=33) pb[31]=binarna(0,pb[30]-1,pb[30]-1);
                                               ~~~~~~^~
horses.cpp:134:17: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
   cnt=fmin(32,td);
                 ^
horses.cpp:134:11: warning: conversion to 'int' from 'double' may alter its value [-Wfloat-conversion]
   cnt=fmin(32,td);
       ~~~~^~~~~~~
horses.cpp:98:12: warning: unused variable 'tmp' [-Wunused-variable]
  long long tmp,r=x[pos];
            ^~~

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