Submission #241655

#	Time	Username	Problem	Language	Result	Execution time	Memory
241655		Nightlight	Horses (IOI15_horses)	C++14	17 / 100	769 ms	25848 KiB

horses

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

const long long MOD = 1e9 +7;

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];
//		cout << 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)]);
	sumX[n] = sumX[L(n)] * sumX[R(n)] % MOD;
}

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_query_modX(int n, int l, int r, int ql, int qr) {
	if(ql <= l && r <= qr) {
		return sumX[n];
	}
	int mid = (l + r) >> 1;
	long long res = 1;
	if(ql <= mid) res *= sum_query_modX(L(n), l, mid, ql, qr);
	if(qr > mid) res *= sum_query_modX(R(n), mid + 1, r, ql, qr);
	return res % MOD;
}

int sum_queryX(int n, int l, int r, int ql, int qr) {
	if(ql <= l && r <= qr) {
		return treeX[n];
	}
	int mid = (l + r) >> 1;
	int res = 1;
	if(ql <= mid) res = kali(res, sum_queryX(L(n), l, mid, ql, qr));
	if(qr > mid) res = kali(res, sum_queryX(R(n), mid + 1, r, ql, qr));
	return res;
}

void buildX() {buildX(1, 0, N);}//cout << "\n";}
void upX(int pos, int val) {upX(1, 0, N, pos, val);}
void findposX() {findposX(1, 0, N);}
long long sum_query_modX(int l, int r) {return (l <= r) && (l >= 0) && (r <= N) ? sum_query_modX(1, 0, N, l, r) : 1;}
long long sum_queryX(int l, int r) {return (l <= r) && (l >= 0) && (r <= N) ? sum_queryX(1, 0, N, l, r) : 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 || pos < 1) 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];
//	cout << "\n";
//	buildX();
	if(last != 1000000001) res = rmqY(1);
	else {
		int l = 0, r = N;
		pointer = 0;
		while(l <= r) {
			int mid = (l + r) >> 1;
			if(sum_queryX(mid, N) == 1000000001) {
				l = mid + 1;
			}else {
				pointer = mid;
				r = mid - 1;
			}
		}
//		cout << sum_queryX(8, 10) << "\n";
//		cout << sum_queryX(9, 10) << "\n";
		res = rmqY(pointer + 1);
		last = sum_queryX(pointer, N);
		sisa = sum_query_modX(0, pointer - 1);
//		cout << 0 << " " << pointer << ": " << sisa << " <=\n";
//		cout << rmqY(pointer + 1) << "\n";
//		cout << pointer << " - \n";
	}
	while(1) {
		now = 1;
		findposX();
		bef *= last / now;
		res = max(res, bef * rmqY(pointer + 1));
//		cout << bef << " " << rmqY(pointer + 1) << " = " << bef * rmqY(pointer + 1) << "\n";
//		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 || pointer >= N) 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) {	
	X[pos] = 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:19: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:61: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:159:20: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   last = sum_queryX(pointer, N);
          ~~~~~~~~~~^~~~~~~~~~~~
horses.cpp:179: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