Submission #96484

#	Time	Username	Problem	Language	Result	Execution time	Memory
96484		figter001	Horses (IOI15_horses)	C++14	100 / 100	1235 ms	69220 KiB

horses

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

using namespace std;

typedef long long ll;
typedef long double ld;
const int maxn = 5e5 + 50;
const int mod = 1e9+7;

ld lgx[maxn],lgy[maxn],seg2[(1<<20)];
ll seg[(1<<20)],y[maxn],x[maxn];
int best[(1<<20)];
int n,l,r;

ld getsum(int n,int s,int e){
	if(s > r || e < l)return 0;
	if(s >= l && e <= r){
		return seg2[n];
	}
	return getsum(n*2,s,(s+e)/2) + getsum(n*2+1,(s+e)/2+1,e);
}

void build1(int n,int s,int e){
	if(s == e){
		seg[n] = x[s];
		seg2[n] = lgx[s];
		return;
	}
	build1(n*2,s,(s+e)/2);
	build1(n*2+1,(s+e)/2+1,e);
	seg[n] = (seg[n*2] * seg[n*2+1])%mod;
	seg2[n] = seg2[n*2] + seg2[n*2+1];
}

void build2(int n,int s,int e){
	if(s == e){
		best[n] = s;
		return;
	}
	build2(n*2,s,(s+e)/2);
	build2(n*2+1,(s+e)/2+1,e);
	l = 1;r = best[n*2];
	ld v = getsum(1,1,::n);
	ld left = v + lgy[r];
	r = best[n*2+1];
	v = getsum(1,1,::n);
	ld right = v + lgy[r];
	if(left >= right)best[n] = best[n*2];
	else best[n] = best[n*2+1];
}


void update1(int n,int s,int e){
	if(s > r || e < l)return;
	if(s == e){
		seg[n] = x[s];
		seg2[n] = lgx[s];
		return;
	}
	update1(n*2,s,(s+e)/2);
	update1(n*2+1,(s+e)/2+1,e);
	seg[n] = (seg[n*2] * seg[n*2+1])%mod;
	seg2[n] = (seg2[n*2] + seg2[n*2+1]);
}

void update2(int n,int s,int e){
	if(s > r || e < l)return;
	if(s == e){
		best[n] = s;
		return;
	}
	update2(n*2,s,(s+e)/2);
	update2(n*2+1,(s+e)/2+1,e);
	l = 1;r = best[n*2];
	ld left = getsum(1,1,::n) + lgy[r];
	r = best[n*2+1];
	ld right = getsum(1,1,::n) + lgy[r];
	if(left >= right)best[n] = best[n*2];
	else best[n] = best[n*2+1];
}
	
ll get(int n,int s,int e){
	if(s > r || e < l)return 1;
	if(s >= l && e <= r)return seg[n];
	return (get(n*2,s,(s+e)/2) * get(n*2+1,(s+e)/2+1,e))%mod;
}

int solve(){
	l = 1;
	r = best[1];
	return (get(1,1,n) * y[r])%mod;
}

int init(int N, int X[], int Y[]){
	n = N;
	for(int i=1;i<=n;i++){
		y[i] = Y[i-1];
		x[i] = X[i-1];
		lgx[i] = log(x[i]);
		lgy[i] = log(y[i]);
	}
	build1(1,1,n);
	build2(1,1,n);
	return solve();
}

int updateX(int pos, int val) {	
	pos++;
	x[pos] = val;
	lgx[pos] = log(x[pos]);
	l = r = pos;
	update1(1,1,n);
	update2(1,1,n);
	return solve();
}

int updateY(int pos, int val) {
	pos++;
	y[pos] = val;
	lgy[pos] = log(y[pos]);
	l = r = pos;
	update2(1,1,n);
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'ld getsum(int, int, int)':
horses.cpp:16:28: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 ld getsum(int n,int s,int e){
                            ^
horses.cpp:14:5: note: shadowed declaration is here
 int n,l,r;
     ^
horses.cpp: In function 'void build1(int, int, int)':
horses.cpp:24:30: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void build1(int n,int s,int e){
                              ^
horses.cpp:14:5: note: shadowed declaration is here
 int n,l,r;
     ^
horses.cpp: In function 'void build2(int, int, int)':
horses.cpp:36:30: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void build2(int n,int s,int e){
                              ^
horses.cpp:14:5: note: shadowed declaration is here
 int n,l,r;
     ^
horses.cpp: In function 'void update1(int, int, int)':
horses.cpp:54:31: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void update1(int n,int s,int e){
                               ^
horses.cpp:14:5: note: shadowed declaration is here
 int n,l,r;
     ^
horses.cpp: In function 'void update2(int, int, int)':
horses.cpp:67:31: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void update2(int n,int s,int e){
                               ^
horses.cpp:14:5: note: shadowed declaration is here
 int n,l,r;
     ^
horses.cpp: In function 'll get(int, int, int)':
horses.cpp:83:25: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 ll get(int n,int s,int e){
                         ^
horses.cpp:14:5: note: shadowed declaration is here
 int n,l,r;
     ^
horses.cpp: In function 'int solve()':
horses.cpp:92:28: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return (get(1,1,n) * y[r])%mod;
         ~~~~~~~~~~~~~~~~~~~^~~~

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