Submission #220933

#	Time	Username	Problem	Language	Result	Execution time	Memory
220933		a_player	Horses (IOI15_horses)	C++14	100 / 100	204 ms	50680 KiB

horses

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

using namespace std;

const int nax=5e5+5;
const int mod=1e9+7;
typedef long long ll;

struct node{
	double lg,lgv;
	int x,y,val;
	
};

node rt[4*nax];
int *X,*Y;
int N;

void updX(int k, int x, int y, int a, int val){
	if(x>a||y<a)return;
	if(x==y){
		rt[k].x=val;
		rt[k].lg=log(val);
		rt[k].val=((ll)val*(ll)rt[k].y)%mod;
		rt[k].lgv=rt[k].lg+log(rt[k].y);
		return;
	}
	int m=(x+y)/2;
	updX(2*k,x,m,a,val);
	updX(2*k+1,m+1,y,a,val);
	rt[k].x=((ll)rt[2*k].x*(ll)rt[2*k+1].x)%mod;
	rt[k].lg=rt[2*k].lg+rt[2*k+1].lg;
	if(rt[2*k].lgv<rt[2*k+1].lgv+rt[2*k].lg){
		rt[k].lgv=rt[2*k+1].lgv+rt[2*k].lg;
		rt[k].val=((ll)rt[2*k].x*(ll)rt[2*k+1].val)%mod;
	}else{
		rt[k].lgv=rt[2*k].lgv;
		rt[k].val=rt[2*k].val;
	}
	
}
void updY(int k, int x, int y, int a, int val){
	if(x>a||y<a)return;
	if(x==y){
		rt[k].y=val;
		rt[k].val=((ll)rt[k].x*(ll)val)%mod;
		rt[k].lgv=rt[k].lg+log(val);
		return;
		}
	int m=(x+y)/2;
	updY(2*k,x,m,a,val);
	updY(2*k+1,m+1,y,a,val);
	rt[k].x=((ll)rt[2*k].x*(ll)rt[2*k+1].x)%mod;
	rt[k].lg=rt[2*k].lg+rt[2*k+1].lg;
	if(rt[2*k].lgv<rt[2*k+1].lgv+rt[2*k].lg){
		rt[k].lgv=rt[2*k+1].lgv+rt[2*k].lg;
		rt[k].val=((ll)rt[2*k].x*(ll)rt[2*k+1].val)%mod;
	}else{
		rt[k].lgv=rt[2*k].lgv;
		rt[k].val=rt[2*k].val;
	}
}
void build(int k, int x, int y){
	if(x==y){
		rt[k].y=Y[x];
		rt[k].x=X[x];
		rt[k].lg=log(X[x]);
		rt[k].lgv=log(Y[x])+rt[k].lg;
		rt[k].val=((ll)rt[k].x*(ll)rt[k].y)%mod;
		return;
	}
	int m=(x+y)/2;
	build(2*k,x,m);
	build(2*k+1,m+1,y);
	rt[k].x=(rt[2*k].x*(ll)rt[2*k+1].x)%mod;
	rt[k].lg=rt[2*k].lg+rt[2*k+1].lg;
	if(rt[2*k].lgv<rt[2*k+1].lgv+rt[2*k].lg){
		rt[k].lgv=rt[2*k+1].lgv+rt[2*k].lg;
		rt[k].val=((ll)rt[2*k].x*(ll)rt[2*k+1].val)%mod;
	}else{
		rt[k].lgv=rt[2*k].lgv;
		rt[k].val=rt[2*k].val;
	}
}

int init(int N, int X[], int Y[]) {
	::N=N;
	::X=X;
	::Y=Y;
	build(1,0,N-1);
	return rt[1].val;
}

int updateX(int pos, int val) {	
	updX(1,0,N-1,pos,val);
	return rt[1].val;
}
int updateY(int pos, int val) {
	updY(1,0,N-1,pos,val);
	return rt[1].val;
}

Compilation message (stderr)

horses.cpp: In function 'void updX(int, int, int, int, int)':
horses.cpp:25:34: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   rt[k].val=((ll)val*(ll)rt[k].y)%mod;
             ~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:32:41: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  rt[k].x=((ll)rt[2*k].x*(ll)rt[2*k+1].x)%mod;
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:36:46: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   rt[k].val=((ll)rt[2*k].x*(ll)rt[2*k+1].val)%mod;
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'void updY(int, int, int, int, int)':
horses.cpp:47:34: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   rt[k].val=((ll)rt[k].x*(ll)val)%mod;
             ~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:54:41: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  rt[k].x=((ll)rt[2*k].x*(ll)rt[2*k+1].x)%mod;
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:58:46: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   rt[k].val=((ll)rt[2*k].x*(ll)rt[2*k+1].val)%mod;
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:70:38: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   rt[k].val=((ll)rt[k].x*(ll)rt[k].y)%mod;
             ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:76:37: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  rt[k].x=(rt[2*k].x*(ll)rt[2*k+1].x)%mod;
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:80:46: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   rt[k].val=((ll)rt[2*k].x*(ll)rt[2*k+1].val)%mod;
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:87:33: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:17:9: note: shadowed declaration is here
 int *X,*Y;
         ^
horses.cpp:87:33: warning: declaration of 'X' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:17:6: note: shadowed declaration is here
 int *X,*Y;
      ^
horses.cpp:87:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:18:5: note: shadowed declaration is here
 int N;
     ^

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