Submission #418633

#	Time	Username	Problem	Language	Result	Execution time	Memory
418633		Chaska	Horses (IOI15_horses)	C++11	20 / 100	784 ms	57676 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define fo(a,b,c) for (int a=b;a<=c;a++)
#define F first
#define S second
using namespace std;
const int MAXN = 5e5+5,mod = 1e9+7;
typedef long long ll;
typedef pair<ll,ll> i2;
int n,x[MAXN],y[MAXN];
ll stX[4*MAXN],r;
i2 stY[4*MAXN];
set<int> Set;
ll ry;
i2 unu;
void iniX(int no,int in,int fin)
{
	if (in == fin) {
		stX[no] = x[in];
		return;
	} 
	int mid=(in+fin)/2;
	iniX(no*2+1,in,mid);
	iniX(no*2+2,mid+1,fin);
	stX[no] = stX[no*2+1]*stX[no*2+2];
	stX[no]%= mod;
	return;
}
void iniY(int no,int in,int fin)
{
	if (in == fin ) {
		stY[no].F = y[in];
		stY[no].S = in;
		return;
	}
	int mid=(in+fin)/2;
	iniY(no*2+1,in,mid);
	iniY(no*2+2,mid+1,fin);
	stY[no] = max(stY[no*2+1],stY[no*2+2]);
	return;

}
void getX(int no,int in,int fin,int u,int v)
{
	if (fin < u || in > v) return;
	if (u<=in && fin <= v){
		r *= stX[no];
		r %= mod;
		return;
	}
	int mid=(in+fin)/2;
	getX(no*2+1,in,mid,u,v);
	getX(no*2+2,mid+1,fin,u,v);
	return;
}
void getY(int no,int in,int fin,int u,int v)
{
	if (fin < u || in > v) return;
	if (u<=in && fin <= v){
		unu = max(unu,stY[no]);
		return;
	}
	int mid=(in+fin)/2;
	getY(no*2+1,in,mid,u,v);
	getY(no*2+2,mid+1,fin,u,v);
	return;
}
void updX(int no,int in,int fin,int u,int v)
{
		if (fin < u || in > u) return;
	if (u<=in && fin <= u){
		stX[no] = v;
		return;
	}
	int mid=(in+fin)/2;
	updX(no*2+1,in,mid,u,v);
	updX(no*2+2,mid+1,fin,u,v);
	stX[no] = stX[no*2+1]*stX[no*2+2];
	stX[no]%= mod;
	return;
}
void updY(int no,int in,int fin,int u,int v)
{
	if (fin < u || in > u) return;
	if (u<=in && fin <= u){
		stY[no].F = v;
		return;
	}
	int mid=(in+fin)/2;
	updY(no*2+1,in,mid,u,v);
	updY(no*2+2,mid+1,fin,u,v);
	stY[no] = max(stY[no*2+1],stY[no*2+2]);
	return;
}
int sol()
{
	ll k = 0; /// respuesta optima, empezando en pos = -1
	ll res = -1; // indice res optima
	ll q=1; // caballos
	

	set<int>::iterator it = Set.end();
	it--;
	vector<int> posres;
	int tp = 0;
	while (true) {

		if (tp > 35) {
			break;
		} else {
			posres.push_back(*it);
			tp++;
			//cout << *it << " ";
			if (it == Set.begin()) { break ;}
			it--;
		}
	}
	reverse(posres.begin(),posres.end());
	posres.push_back(n);


	if (posres.size()==1) {
		unu.F=0;
		unu.S = -1;
		getY(0,0,n-1,0,n-1);
		return unu.F;
	} else {

	//	for (int u : posres) cout << u <<" " ;
	for (int j=0;j<(int)posres.size()-1;j++) {
		int i = posres[j];
		ll ok = x[i];
		ll owo = posres[j+1]-1;
		unu.F = 0;
		unu.S = -1;
		getY(0,0,n-1,i,owo);
		//cout << unu << " " ;
		q *= ok;
		if (k<=q) {
			res = unu.S;
			k = unu.F;
			q = 1;
		} else {
			q *= unu.F;
			if (k<=q) {
				res = unu.S;
				k = unu.F;
				q = 1;
			} else {
				q /= unu.F;
			}
		}
	}
	

	r=1;
	getX(0,0,n-1,0,res);
	r %= mod;
	r *= y[res];
	r %= mod;
	return r;
	}
}
int init(int N, int X[], int Y[]) {
	n = N;
	
	fo(i,0,n-1) x[i] = X[i];
	fo(i,0,n-1) y[i] = Y[i];
	fo(i,0,n-1) if (x[i] != 1) Set.insert(i);
	iniX(0,0,n-1);
	iniY(0,0,n-1);
	return sol();
}

int updateX(int pos, int val) {	
	if (x[pos] == 1 && val > 1) Set.insert(pos);
	else {
		if (x[pos] > 1 && val == 1) {
			Set.erase(pos);
		}
	}
	x[pos] = val;
	updX(0,0,n-1,pos,val);
	return sol();
}

int updateY(int pos, int val) {
	y[pos] = val;
	updY(0,0,n-1,pos,val);
	return sol();
}

Compilation message (stderr)

horses.cpp: In function 'int sol()':
horses.cpp:4:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    4 | #define F first
      |           ^
horses.cpp:126:14: note: in expansion of macro 'F'
  126 |   return unu.F;
      |              ^
horses.cpp:136:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  136 |   getY(0,0,n-1,i,owo);
      |                  ^~~
horses.cpp:157:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  157 |  getX(0,0,n-1,0,res);
      |                 ^~~
horses.cpp:161:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  161 |  return r;
      |         ^

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