Submission #241643

#	Time	Username	Problem	Language	Result	Execution time	Memory
241643		Nightlight	Horses (IOI15_horses)	C++14	17 / 100	532 ms	26620 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define L(n) (n << 1)
#define R(n) (n << 1 | 1)
#define MOD 1000000007LL
using namespace std;

int N;
int X[500005], Y[500005];
int treeX[2000000];
long long sumX[2000000];
int mxY[2000000];
int last, now;//product sum suffix skrg
int pointer;//posisi suffix skrg
int residue;//product sum % MOD prefix skrg
//segtree 2 buah dan 1 BIT nice
int kali(long long a, long long b) {
	return a * b > 1000000000 ? 1000000001 : a * b;
}

//segtreeX
void buildX(int n, int l, int r) {
	if(l == r) {
		treeX[n] = X[l];
		sumX[n] = X[l];
		return;
	}
	int mid = (l + r) >> 1;
	buildX(L(n), l, mid);
	buildX(R(n), mid + 1, r);
	treeX[n] = kali(treeX[L(n)], treeX[R(n)]);
}

void upX(int n, int l, int r, int pos, int val) {
	if(l == r) {
		treeX[n] = val;
		sumX[n] = val;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) upX(L(n), l, mid, pos, val);
	else upX(R(n), mid + 1, r, pos, val);
	treeX[n] = kali(treeX[L(n)], treeX[R(n)]);
	sumX[n] = sumX[L(n)] * sumX[R(n)] % MOD;
}
//query mencari suffix terpanjang yang product sumnya < sum suffix sekarang
void findposX(int n, int l, int r, long long need = last) {
//	cout << l << " " << r << " " << need << "\n";
//	cout << treeX[L(n)] << " " << treeX[R(n)] << "\n";
	if(l == r) {
		pointer = l;
		return;
	}
	int mid = (l + r) >> 1;
	if(treeX[R(n)] >= need) findposX(R(n), mid + 1, r, need);
	else {
		now *= treeX[R(n)];
		need = ceil((double) need / treeX[R(n)]);
		findposX(L(n), l, mid, need);
	}
}

long long sum_queryX(int n, int l, int r, int pos) {
	if(r <= pos) {
		return sumX[n];
	}
	int mid = (l + r) >> 1;
	long long res = sum_queryX(L(n), l, mid, pos);
	if(pos > mid) res *= sum_queryX(R(n), mid + 1, r, pos);
	return res % MOD;
}

void buildX() {buildX(1, 0, N);}
void upX(int pos, int val) {upX(1, 0, N, pos, val);}
void findposX() {findposX(1, 0, N);}
long long sum_queryX(int pos) {return pos >= 0 ? sum_queryX(1, 0, N, pos) : 1;}
//segtree X end
//segtree Y

void buildY(int n, int l, int r) {
	if(l == r) {
		mxY[n] = Y[l];
		return;
	}
	int mid = (l + r) >> 1;
	buildY(L(n), l, mid);
	buildY(R(n), mid + 1, r);
	mxY[n] = max(mxY[L(n)], mxY[R(n)]);
}

void upY(int n, int l, int r, int pos, int val) {
	if(l == r) {
		mxY[n] = val;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) upY(L(n), l, mid, pos, val);
	else upY(R(n), mid + 1, r, pos, val);
	mxY[n] = max(mxY[L(n)], mxY[R(n)]);
}

int rmqY(int n, int l, int r, int pos) {
	if(pos <= l) return mxY[n];
	int mid = (l + r) >> 1;
	int res = 0;
	if(pos <= mid) res = rmqY(L(n), l, mid, pos);
	res = max(res, rmqY(R(n), mid + 1, r, pos));
	return res;
}

void buildY() {buildY(1, 1, N);}
void upY(int pos, int val) {upY(1, 1, N, pos, val);}
int rmqY(int pos) {
	if(pos > N) return 0;
	return rmqY(1, 1, N, pos);
}

//segtree Y end

int solve() {
	long long res = 1;	
	long long bef = 1;
	long long sisa = 1;
	last = treeX[1];
	if(last != 1000000001) res = rmqY(1);
	while(1) {
		now = 1;
		findposX();
		bef *= last / now;
		if(last == 1000000001) {
			sisa = sum_queryX(pointer - 1);
//			cout << pointer - 1 << "\n";
//			cout << sisa << "\n";
		}
		res = max(res, bef * rmqY(pointer + 1));
//		cout << "sum sebelumnya: " << last << "\n";
//		cout << "sum sekarang: " << now << "\n";
//		cout << "posisi skrg: " << pointer << "\n";
//		cout << "bef: " << bef << "\n";
//		cout << "best di array Y di range "<< pointer + 1 << " " << N << " : " << rmqY(pointer + 1) << "\n\n";
		if(now == 1) break;
		swap(now, last);
	}
	return (res % MOD * sisa % MOD);
}

int init(int n, int x[], int y[]) {
	N = n;
	for(int i = 0; i < N; i++) X[i] = x[i], Y[i + 1] = y[i];
	X[N] = 1;
	buildX();
	buildY();
	return solve();
}

int updateX(int pos, int val) {	
	upX(pos, val);
	return solve();
}

int updateY(int pos, int val) {
	upY(pos + 1, val);
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'int kali(long long int, long long int)':
horses.cpp:18:28: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return a * b > 1000000000 ? 1000000001 : a * b;
         ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'void findposX(int, int, int, long long int)':
horses.cpp:58:14: warning: conversion to 'long long int' from 'double' may alter its value [-Wfloat-conversion]
   need = ceil((double) need / treeX[R(n)]);
          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int solve()':
horses.cpp:144:27: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (res % MOD * sisa % MOD);
         ~~~~~~~~~~~~~~~~~~^~~~~~

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