Submission #96442

#	Time	Username	Problem	Language	Result	Execution time	Memory
96442		figter001	Horses (IOI15_horses)	C++14	17 / 100	1565 ms	77568 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)],y[maxn],x[maxn],val2;
int n,l,r;
 
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 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] = x[s];
		return;
	}
	build2(n*2,s,(s+e)/2);
	build2(n*2+1,(s+e)/2+1,e);
	seg[n] = (seg[n*2] * seg[n*2+1])%mod;
}
 
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){
	if(s > r || e < l)return;
	if(s >= l && e <= r){
		seg[n] = x[s];
		return;
	}
	update2(n*2,s,(s+e)/2);
	update2(n*2+1,(s+e)/2+1,e);
	seg[n] = (seg[n*2] * seg[n*2+1])%mod;
}
	
int get(int n,int s,int e){
	if(s > r || e < l)return 1;
	if(s >= l && e <= r)return (int)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 = lgs[1].second;
	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];
		sum[i] = sum[i-1] + log((ld)x[i]);
	}
	build1(1,1,n);
	build2(1,1,n);
	return solve();
}
 
int updateX(int pos, int val) {	
	pos++;
	val1 = log((ld)val) - log((ld)x[pos]);
	x[pos] = val;
	l = pos;
	r = n;
	update1(1,1,n);
	l = r = pos;
	update2(1,1,n);
	return solve();
}
 
int updateY(int pos, int val) {
	pos++;
	val1 = log((ld)val) - log((ld)y[pos]);
	y[pos] = val;
	l = r = pos;
	update1(1,1,n);
	for(int i=1;i<=n;i++){
		l = r = i;
		update1(1,1,n);
	}
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'void pro1(int, int, int)':
horses.cpp:16: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 build1(int, int, int)':
horses.cpp:25: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:35: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:45: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:58: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:69: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;
     ^
horses.cpp: In function 'int solve()':
horses.cpp:78: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: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23