이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007LL
#include "horses.h"
//hypothesis 1: There is no point in keeping a partial amount of horses. Sell all, or don't bother.
//Let's test this.
//Ok, should be confirmed (passed subtask 1)
//now, running product of X can be really big
//we need to determine the largest value in meow, where meow[i] = Y[i] * prefixProdX[i];
//honestly even Y[i] can be really big (10^9 for both X and Y)
//I also don't really want to touch floating point
//let our two comparison indices be A and B
//without loss of generality, let A < B
//then meow[A] = Y[A] * prefixProdX[A], meow[B] = Y[B] * prefixProdX[B]
//meow[A] < meow[B] iff
//Y[A] * prefixProdX[A] < Y[B] * prefixProdX[B]
//Y[A] < Y[B] * prefixProdX[B] / prefixProdX[A]
//Y[A] < Y[B] * rangeProdX(A+1, B)
//hmm both Y[A] and Y[B] are bounded by 10^9
//meaning if rangeProdX(A+1, B) ever exceeds 10^9, we can safely say meow[B] is greater
//Y is also bounded by 1
#define int long long
#define actlint int32_t
actlint *X, *Y;
int N;
bool st3 = true;
#define MAXN 500001
#define makeMid int mid = (s+e)/2
#define lc(x) (2*x)
#define rc(x) (2*x+1)
#define parent(x) (x/2)
typedef int stdata;
stdata ST[4*MAXN+1] = {0};
inline stdata combine(stdata x, stdata y){
return (x*y)%MOD;
}
void pointSet(int x, stdata y, int index=1, int s=0, int e=N-1){
makeMid;
if (s==e){ ST[index] = y; return; }
if (x <= mid) pointSet(x, y, lc(index), s, mid);
else pointSet(x, y, rc(index), mid+1, e);
ST[index] = combine(ST[lc(index)], ST[rc(index)]);
}
void pointAdd(int x, stdata y, int index=1, int s=0, int e=N-1){
makeMid;
if (s==e){ ST[index] += y; return; }
if (x <= mid) pointAdd(x, y, lc(index), s, mid);
else pointAdd(x, y, rc(index), mid+1, e);
ST[index] = combine(ST[lc(index)], ST[rc(index)]);
}
stdata query(int x, int y, int index=1, int s=0, int e=N-1){
makeMid;
if (s==x && e==y) return ST[index];
if (x <= mid && y > mid) return combine(query(x, mid, lc(index), s, mid), query(mid+1, y, rc(index), mid+1, e));
else if (x <= mid) return query(x, y, lc(index), s, mid);
else return query(x, y, rc(index), mid+1, e);
}
int calc(){
//this is bottleneck of code
//this takes O(N) time, which is too long since we cannot afford O(NM)
//problem that this is meant to solve:
//find max of Y[i] * prefixProdX[i] (in log n time?)
long long best = 0;
long long run = 1;
long long init = 0;
if (st3) init = max(N-33LL, 0LL), best = max(N-33LL, 0LL);
for (int i = init; i < N; i++){
run *= X[i];
if ((int)Y[best] < (int)Y[i] * run){
best = i;
run = 1;
}
}
run = query(0, best);
run *= Y[best]; run %= MOD;
return run;
}
actlint init(actlint hmN, actlint hmX[], actlint hmY[]) {
N = hmN;
X = hmX; Y = hmY;
for (int i = 0; i < N; i++){
if (X[i] < 2) st3 = false;
pointSet(i, X[i]);
}
return calc();
}
actlint updateX(actlint pos, actlint val) {
X[pos] = val;
if (val < 2) st3 = false;
pointSet(pos, val);
return calc();
}
actlint updateY(actlint pos, actlint val) {
Y[pos] = val;
return calc();
}
컴파일 시 표준 에러 (stderr) 메시지
horses.cpp: In function 'int32_t init(int32_t, int32_t*, int32_t*)':
horses.cpp:104:13: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
104 | return calc();
| ~~~~^~
horses.cpp: In function 'int32_t updateX(int32_t, int32_t)':
horses.cpp:111:13: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
111 | return calc();
| ~~~~^~
horses.cpp: In function 'int32_t updateY(int32_t, int32_t)':
horses.cpp:116:13: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
116 | return calc();
| ~~~~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |