Submission #417369

#	Time	Username	Problem	Language	Result	Execution time	Memory
417369		victoriad	Horses (IOI15_horses)	C++14	100 / 100	1000 ms	76868 KiB

horses

#include "horses.h"
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <utility>
#include <stack>
#include <vector>
#include <fstream>
#include <set>
#include <map>

using namespace std;
const int mod=1e9+7;
typedef long long int ll;
vector<ll>lx;
vector<ll>ly;
vector<ll>mu;
vector<ll>ma;
set<int>s;

int hI(int p){
	return p<<1;
}
int hD(int p){
	return (p<<1)+1;
}

void buildmu(int nodo,int L,int R){
	if(L<R){
		int m=L+(R-L)/2;
		buildmu(hI(nodo),L,m);
		buildmu(hD(nodo),m+1,R);
		mu[nodo]=(mu[hI(nodo)]*mu[hD(nodo)])%mod;
	}
	else{
		mu[nodo]=lx[L];
	}
}


void buildma(int nodo,int L,int R){
	if(L<R){
		int m=L+(R-L)/2;
		buildma(hI(nodo),L,m);
		buildma(hD(nodo),m+1,R);
		ma[nodo]=max(ma[hI(nodo)],ma[hD(nodo)]);
	}
	else{
		ma[nodo]=ly[L];
	}
}
ll vama(int L,int R,int st,int fi,int nodo){
	if(L>=st && R<=fi)return ma[nodo];
	else if(st>R || fi<L)return -1;
	else{
		int m=L+(R-L)/2;
		ll v1=vama(L,m,st,fi,hI(nodo));
		ll v2=vama(m+1,R,st,fi,hD(nodo));
		return max(v1,v2);
	}
}
ll vamu(int L,int R,int st,int fi,int nodo){
	if(L>=st && R<=fi)return mu[nodo];
	else if(st>R || fi<L)return 1;
	else{
		int m=L+(R-L)/2;
		ll v1=vamu(L,m,st,fi,hI(nodo));
		ll v2=vamu(m+1,R,st,fi,hD(nodo));
		return (v1*v2)%mod;
	}
}

void upY(int nodo,int L,int R,int b,ll n){
	if(b<L||b>R)return;
	else if(L==R){
		ly[b]=n;
		ma[nodo]=n;
	}
	else{
		int m=L+(R-L)/2;
		upY(hI(nodo),L,m,b,n);
		upY(hD(nodo),m+1,R,b,n);
		ma[nodo]=max(ma[hI(nodo)],ma[hD(nodo)]);
	}
}

void upX(int nodo,int L,int R,int b,ll n){
	if(b<L||b>R)return;
	else if(L==R){
		lx[b]=n;
		mu[nodo]=n;
	}
	else{
		int m=L+(R-L)/2;
		upX(hI(nodo),L,m,b,n);
		upX(hD(nodo),m+1,R,b,n);
		mu[nodo]=(mu[hI(nodo)]*mu[hD(nodo)])%mod;
	}
}

int solve(){
	int n=lx.size();
	ll l,r=n-1,a=0,me=0;
	for(ll k:s){
		l=-1*k;
		a=vama(0,n-1,l,r,1);
		me=max(me,a);
		me*=lx[l];
		r=l-1;
		if(me>1e9||l==0)break;
	}
	me%=mod;
	if(r>=0){
		me=(me*vamu(0,n-1,0,r,1))%mod;
	}
	return me;
}

int init(int N, int X[], int Y[]) {
lx.resize(N);
ly.resize(N);
mu.resize(4*N);
ma.resize(4*N);
for(int i=0;i<N;i++){
	lx[i]=X[i];
	ly[i]=Y[i];
	if(X[i]>1){
		s.insert(-1*i);
	}
}	
s.insert(0);
buildmu(1,0,N-1);
buildma(1,0,N-1);
return solve();
}
 
int updateX(int pos, int val) {
	int n=lx.size();
	if(pos!=0){
	ll j=lx[pos];
	if(j==1 && val>1){
		s.insert(-1*pos);
	}
	else if(val==1 && j>1){
		s.erase(-1*pos);
	}
	}
	lx[pos]=val;
	upX(1,0,n-1,pos,val);
	return solve();
}
 
int updateY(int pos, int val) {
	int n=lx.size();
	ly[pos]=val;
	upY(1,0,n-1,pos,val);
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'int solve()':
horses.cpp:103:15: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  103 |  int n=lx.size();
      |        ~~~~~~~^~
horses.cpp:107:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  107 |   a=vama(0,n-1,l,r,1);
      |                ^
horses.cpp:107:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  107 |   a=vama(0,n-1,l,r,1);
      |                  ^
horses.cpp:111:6: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
  111 |   if(me>1e9||l==0)break;
      |      ^~
horses.cpp:115:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  115 |   me=(me*vamu(0,n-1,0,r,1))%mod;
      |                       ^
horses.cpp:117:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  117 |  return me;
      |         ^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:139:15: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  139 |  int n=lx.size();
      |        ~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:155:15: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  155 |  int n=lx.size();
      |        ~~~~~~~^~

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