제출 #96407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96407		figter001	말 (IOI15_horses)	C++17	17 / 100	233 ms	62220 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],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] = x[s]%mod;
		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){
	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 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);
}

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]);
	val2 = (val * Pow(x[pos],mod-2))%mod;
	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);
	return solve();
}

컴파일 시 표준 에러 (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:62: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:75: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:87: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:97: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