Submission #82051

#	Time	Username	Problem	Language	Result	Execution time	Memory
82051		GioChkhaidze	Horses (IOI15_horses)	C++14	100 / 100	644 ms	108548 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

#define Tree int h,int l,int r
#define left 2*h,l,(l+r)/2
#define right 2*h+1,(l+r)/2+1,r
#define Pb push_back
#define Mp make_pair
#define F first
#define S second

long long inf=2000000008;
long long Mod=1000000007;
int n,x[500002],y[500002],ANS;

int v[2000002];
int V[2000002];
int Suf[2000002];
int Pre[2000002];

int L,R;

int Pro(Tree)
{
	if (L>r || l>R) return 1;
	if (L<=l && r<=R) return v[h];
	
	return (1LL*Pro(left)*Pro(right))%Mod;
}

void UpPro(Tree)
{
	if (l>L || r<L) return ;
	if (L==l && r==L) { v[h]=R%Mod; return ; }
	
	UpPro(left);
	UpPro(right);
	
	v[h]=(1LL*v[2*h]*v[2*h+1])%Mod;
}

void Upd(Tree)
{
	if (L>r || L<l) return ;
	if (L==l && L==r)
	{
		V[h]=L;
		Pre[h]=R;
		Suf[h]=1;
		return ;
	}
	
	Upd(left);
	Upd(right);
		
	if (y[V[2*h]]<1LL*min(inf,1LL*Suf[2*h]*Pre[2*h+1])*y[V[2*h+1]])
	{
		V[h]=V[2*h+1];
		Pre[h]=min(min(1LL*Pre[2*h]*Suf[2*h],inf)*Pre[2*h+1],inf);
		Suf[h]=Suf[2*h+1];
	}
		else
	{
		V[h]=V[2*h];
		Pre[h]=Pre[2*h];
		Suf[h]=min(min(1LL*Pre[2*h+1]*Suf[2*h+1],inf)*Suf[2*h],inf);
	}		
}

pair < int , pair < int , int > > Get(Tree)
{
	if (L>r || l>R) return Mp(0,Mp(1,1));
	if (L<=l && r<=R) return Mp(V[h],Mp(Pre[h],Suf[h]));
	
	pair < int , pair < int , int > > X1=Get(left);
	pair < int , pair < int , int > > X2=Get(right);
	
	if (y[X1.F]<min(1LL*y[X2.F]*min(1LL*X2.S.F*X1.S.S,inf),inf))
		return Mp(X2.F,Mp(min(1LL*min(1LL*X1.S.F*X1.S.S,inf)*X2.S.F,inf),X2.S.S));
	
	if (y[X1.F]>=min(1LL*y[X2.F]*min(1LL*X2.S.F*X1.S.S,inf),inf))
		return Mp(X1.F,Mp(X1.S.F,min(1LL*min(1LL*X2.S.F*X2.S.S,inf)*X1.S.S,inf)));
}

int init(int N, int X[], int Y[]) {

	n=N;
	
	for (int i=1; i<=n; i++)
		x[i]=X[i-1],y[i]=Y[i-1];
	
	for (int i=1; i<=n; i++) {
		L=i; R=x[i]; 
		Upd(1,1,n);
		UpPro(1,1,n);
	}

	L=1; R=n;

	R=Get(1,1,n).F; L=1;

	return (1LL*Pro(1,1,n)*y[R])%Mod;
}

int updateX(int pos, int val) {	
	
	pos++;
	
	L=pos; R=val; 

	x[pos]=val;
			
	Upd(1,1,n);
	UpPro(1,1,n);
	
	L=1; R=n;
	R=Get(1,1,n).F;	L=1;	
			
	return  (1LL*Pro(1,1,n)*y[R])%Mod;
}

int updateY(int pos, int val) {
	
	pos++;
	
	L=pos; R=x[pos]; 
	
	y[pos]=val;
	
	Upd(1,1,n);
	
	L=1; R=n;
	R=Get(1,1,n).F;	L=1; 	
			
	return  (1LL*Pro(1,1,n)*y[R])%Mod;
}

Compilation message (stderr)

horses.cpp: In function 'int Pro(int, int, int)':
horses.cpp:29:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (1LL*Pro(left)*Pro(right))%Mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'void UpPro(int, int, int)':
horses.cpp:35:28: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  if (L==l && r==L) { v[h]=R%Mod; return ; }
                           ~^~~~
horses.cpp:40:28: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  v[h]=(1LL*v[2*h]*v[2*h+1])%Mod;
       ~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'void Upd(int, int, int)':
horses.cpp:60:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   Pre[h]=min(min(1LL*Pre[2*h]*Suf[2*h],inf)*Pre[2*h+1],inf);
          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:67:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   Suf[h]=min(min(1LL*Pre[2*h+1]*Suf[2*h+1],inf)*Suf[2*h],inf);
          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:103:30: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (1LL*Pro(1,1,n)*y[R])%Mod;
         ~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:120:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return  (1LL*Pro(1,1,n)*y[R])%Mod;
          ~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:136:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return  (1LL*Pro(1,1,n)*y[R])%Mod;
          ~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'std::pair<int, std::pair<int, int> > Get(int, int, int)':
horses.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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