Submission #387158

#	Time	Username	Problem	Language	Result	Execution time	Memory
387158		alireza_kaviani	Horses (IOI15_horses)	C++11	100 / 100	371 ms	65132 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;

typedef long long ll;

const ll MAXN = 5e5 + 10;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 5;

ll n , x[MAXN] , y[MAXN] , mul[MAXN * 2] , mx[MAXN * 2];
set<int , greater<int>> st;

void reBuild(int pos){
	for(mul[pos + n] = x[pos] , mx[pos + n] = y[pos] , pos += n ; pos /= 2 ;){
		mul[pos] = mul[pos * 2] * mul[pos * 2 + 1] % MOD;
		mx[pos] = max(mx[pos * 2] , mx[pos * 2 + 1]); 
	}
}

ll getMul(int ql , int qr){
	ll ans = 1;
	for(ql += n , qr += n ; ql < qr ; ql >>= 1 , qr >>= 1){
		if(ql & 1)	ans = ans * mul[ql++] % MOD;
		if(qr & 1)	ans = ans * mul[--qr] % MOD;
	}
	return ans;
}

ll getMax(int ql , int qr){
	ll ans = 0;
	for(ql += n , qr += n ; ql < qr ; ql >>= 1 , qr >>= 1){
		if(ql & 1)	ans = max(ans , mx[ql++]);
		if(qr & 1)	ans = max(ans , mx[--qr]);
	}
	return ans;
}

ll solve(){
	ll ans = 0 , cur = n , prv;
	for(auto it = st.begin() ; it != st.end() ; it++){
		if(ans > INF)	break;
		prv = cur; cur = (*it);
		ans = max(ans , getMax(cur , prv)) * x[cur];
//		cout << cur << ' ' << getMax(cur , prv) << endl;
	}
//	cout << endl;
	return ans % MOD * getMul(0 , cur) % MOD;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for(int i = 0 ; i < N ; i++){
		mul[i + N] = X[i]; x[i] = X[i];
		mx[i + N] = Y[i];  y[i] = Y[i];
		if(X[i] >= 2 || i == 0)	st.insert(i);
	}
	for(int i = N - 1 ; i >= 1 ; i--){
		mul[i] = mul[i * 2] * mul[i * 2 + 1] % MOD;
		mx[i] = max(mx[i * 2] , mx[i * 2 + 1]);
	}
	return solve();
}

int updateX(int pos, int val) {	
	x[pos] = val; st.erase(pos);
	reBuild(pos);
	if(val >= 2 || pos == 0)	st.insert(pos);
	return solve();
}

int updateY(int pos, int val) {
	y[pos] = val;
	reBuild(pos);
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'void reBuild(int)':
horses.cpp:15:57: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   15 |  for(mul[pos + n] = x[pos] , mx[pos + n] = y[pos] , pos += n ; pos /= 2 ;){
      |                                                     ~~~~^~~~
horses.cpp: In function 'll getMul(int, int)':
horses.cpp:23:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   23 |  for(ql += n , qr += n ; ql < qr ; ql >>= 1 , qr >>= 1){
      |      ~~~^~~~
horses.cpp:23:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   23 |  for(ql += n , qr += n ; ql < qr ; ql >>= 1 , qr >>= 1){
      |                ~~~^~~~
horses.cpp: In function 'll getMax(int, int)':
horses.cpp:32:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   32 |  for(ql += n , qr += n ; ql < qr ; ql >>= 1 , qr >>= 1){
      |      ~~~^~~~
horses.cpp:32:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   32 |  for(ql += n , qr += n ; ql < qr ; ql >>= 1 , qr >>= 1){
      |                ~~~^~~~
horses.cpp: In function 'll solve()':
horses.cpp:44:26: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   44 |   ans = max(ans , getMax(cur , prv)) * x[cur];
      |                          ^~~
horses.cpp:44:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   44 |   ans = max(ans , getMax(cur , prv)) * x[cur];
      |                                ^~~
horses.cpp:48:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   48 |  return ans % MOD * getMul(0 , cur) % MOD;
      |                                ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:62:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   62 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:69:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   69 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:75:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   75 |  return solve();
      |         ~~~~~^~

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