Submission #96404

#	Time	Username	Problem	Language	Result	Execution time	Memory
96404		figter001	Horses (IOI15_horses)	C++17	17 / 100	337 ms	63988 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;

pair<ld,int> lgs[(1<<20)];
ld sum[maxn],lazy1[(1<<20)],val1;
ll seg[(1<<20)],mul[maxn],y[maxn],x[maxn],lazy2[(1<<20)],val2;
int n,l,r;

ll Pow(ll a,ll b){
	if(!b)return 1;
	ll ret = Pow(a,b/2);
	if(b%2)return ((ret*ret)%mod*a)%mod;
	return (ret&ret)%mod;
}

void pro1(int n,int s,int e){
	lgs[n].first += lazy1[n];
	if(s != e){
		lazy1[n*2] += lazy1[n];
		lazy1[n*2+1] += lazy1[n];
	}
	lazy1[n] = 0;
}

void pro2(int n,int s,int e){
	if(!lazy2[n])lazy2[n] = 1;
	seg[n] = (seg[n] * lazy2[n])%mod;
	if(s != e){
		lazy2[n*2] = (lazy2[n*2] * lazy2[n])%mod;
		lazy2[n*2+1] = (lazy2[n*2+1] * lazy2[n])%mod;
	}
	lazy2[n] = 0;
}

void build1(int n,int s,int e){
	if(s == e){
		lgs[n] = {sum[s] + log((ld)y[s]),s};
		return;
	}
	build1(n*2,s,(s+e)/2);
	build1(n*2+1,(s+e)/2+1,e);
	lgs[n] = max(lgs[n*2],lgs[n*2+1]);
}

void build2(int n,int s,int e){
	if(s == e){
		seg[n] = (mul[s] * y[s])%mod;
		return;
	}
	build2(n*2,s,(s+e)/2);
	build2(n*2+1,(s+e)/2+1,e);
}

void update1(int n,int s,int e){
	pro1(n,s,e);
	if(s > r || e < l)return;
	if(s >= l && e <= r){
		lazy1[n] += val1;
		pro1(n,s,e);
		return;
	}
	update1(n*2,s,(s+e)/2);
	update1(n*2+1,(s+e)/2+1,e);
	lgs[n] = max(lgs[n*2],lgs[n*2+1]);
}

void update2(int n,int s,int e){
	pro2(n,s,e);
	if(s > r || e < l)return;
	if(s >= l && e <= r){
		lazy2[n] = (lazy2[n] * val2)%mod;;
		pro2(n,s,e);
		return;
	}
	update2(n*2,s,(s+e)/2);
	update2(n*2+1,(s+e)/2+1,e);
}

int get(int n,int s,int e){
	pro2(n,s,e);
	if(s > r || e < l)return 0;
	if(s == e)return (int)seg[n];
	return max(get(n*2,s,(s+e)/2) , get(n*2+1,(s+e)/2+1,e));
}

int solve(){
	l = r = lgs[1].second;
	return get(1,1,n);
}

int init(int N, int X[], int Y[]){
	n = N;
	mul[0] = 1;
	for(int i=1;i<=n;i++){
		y[i] = Y[i-1];
		x[i] = X[i-1];
		sum[i] = sum[i-1] + log((ld)x[i]);
		mul[i] = (mul[i-1] * x[i])%mod;
	}
	build1(1,1,n);
	build2(1,1,n);
	return solve();
}

int updateX(int pos, int val) {	
	pos++;
	ld dif = log((ld)val) - log((ld)x[pos]);
	val2 = (val * Pow(x[pos],mod-2))%mod;
	x[pos] = val;
	l = pos;
	r = n;
	val1 = dif;
	update1(1,1,n);
	update2(1,1,n);
	return solve();
}

int updateY(int pos, int val) {
	pos++;
	ld dif = log((ld)val) - log((ld)y[pos]);
	val2 = (val * Pow(y[pos],mod-2))%mod;
	y[pos] = val;
	l = r = pos;
	val1 = dif;
	update1(1,1,n);
	update2(1,1,n);
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'void pro1(int, int, int)':
horses.cpp:23:28: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void pro1(int n,int s,int e){
                            ^
horses.cpp:14:5: note: shadowed declaration is here
 int n,l,r;
     ^
horses.cpp: In function 'void pro2(int, int, int)':
horses.cpp:32:28: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void pro2(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:42: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:52: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:61: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:74: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 'int get(int, int, int)':
horses.cpp:86:26: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 int get(int n,int s,int e){
                          ^
horses.cpp:14:5: note: shadowed declaration is here
 int n,l,r;
     ^

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