제출 #738980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
738980		shoryu386	말 (IOI15_horses)	C++17	54 / 100	1560 ms	26076 KiB

horses

#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();
      |         ~~~~^~

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