Submission #414795

#	Time	Username	Problem	Language	Result	Execution time	Memory
414795		Bill_00	Horses (IOI15_horses)	C++14	0 / 100	94 ms	40260 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;
long long y[500005],x[500005],rightt[500005],leftt[500005];
long long pro[5000000],n,mx[5000000];
set<pair<ll,ll> >s;
void build1(long long id,long long l,long long r){
	if(l==r){
		mx[id]=y[l];
		return;
	}
	ll m=(l+r)>>1;
	build1(id*2,l,m);
	build1(id*2+1,m+1,r);
	mx[id]=max(mx[id*2],mx[id*2+1]);
}
void build(long long id,long long l,long long r){
	if(l==r){
		pro[id]=y[l];
		return;
	}
	long long m=(l+r)>>1;
	build(id*2,l,m);
	build(id*2+1,m+1,r);
	pro[id]=pro[id*2]*pro[id*2+1];
	if(pro[id]>=MOD) pro[id]%=MOD;
}
long long query(long long id,long long l,long long r,long long L,long long R){
	if(R<L) return 1;
	if(r<L || R<l) return 1;
	if(L<=l && r<=R) return pro[id];
	long long m=(l+r)>>1;
	return (query(id*2,l,m,L,R)*query(id*2+1,m+1,r,L,R))%MOD;
}
long long query1(ll id,ll l,ll r,ll L,ll R){
	if(R<l || r<L) return 0;
	if(L<=l && r<=R) return mx[id];
	ll m=(l+r)>>1;
	return max(query1(id*2,l,m,L,R),query1(id*2+1,m+1,r,L,R));
}
void update(ll id,ll l,ll r,ll d,ll e){
	if(l==r){
		pro[id]=e;
		return;
	}
	ll m=(l+r)>>1;
	if(m>=d) update(id*2,l,m,d,e);
	else update(id*2+1,m+1,r,d,e);
	pro[id]=pro[id*2]*pro[id*2+1];
	if(pro[id]>=MOD) pro[id]%=MOD;
}
void update1(ll id,ll l,ll r,ll d,ll e){
	if(l==r){
		mx[id]=e;
		return;
	}
	ll m=(l+r)>>1;
	if(m>=d) update1(id*2,l,m,d,e);
	else update1(id*2+1,m+1,r,d,e);
	mx[id]=max(mx[id*2],mx[id*2+1]);
}
int init(int N,int X[],int Y[]){
	memset(leftt,-1,sizeof(leftt));
	memset(rightt,-1,sizeof(rightt));
	n=(long long)N;
	for(long long i=0;i<n;i++){
		y[i]=(long long)Y[i];
		x[i]=(long long)X[i];	
	} 
	build(1,0,n-1);
	build1(1,0,n-1);
	bool flag=0;
	long long l;
	for(long long i=0;i<n;i++){
		if(x[i]==1 && flag==0){
			flag=1;
			l=i;
		}
		if(x[i]!=1 && flag==1){
			flag=0;
			s.insert({l,i-1});
			rightt[l]=i-1;
			leftt[i-1]=l;
		}
	}
	if(flag==1){
		rightt[l]=n-1;
		leftt[n-1]=l;
		s.insert({l,n-1});
	}
	long long c=y[n-1];
	pair<long double,ll>p={0,-1};
	for(ll i=n-1;i>=0;i--){
		ll val=y[i];
		if(leftt[i]==-1){
			i=leftt[i];
			val=query1(1,0,n-1,i,rightt[i]);	
		} 
		p=max(p,{(long double)(c)/(long double)(val),i});
		c*=x[i];
		if(c>=1000000000) break;
	}
	ll ans=query(1,0,n-1,0,p.second);
	ll id=p.second,val=y[id];
	if(rightt[id]!=-1) val=query1(1,0,n-1,id,rightt[id]);
	return (ans*val)%MOD;
}

int updateX(int pos, int val){
	update(1,0,n-1,pos,val);
	x[pos]=val;
	if(val==1){
		pair<ll,ll>temp={pos,1000000000};
		auto it=s.lower_bound(temp);
		--it;
		if(it->first>pos || pos>it->second){
			leftt[pos]=pos;
			rightt[pos]=pos;
			s.insert({leftt[pos],rightt[pos]});
			if(pos>0 && leftt[pos-1]!=-1){
				rightt[leftt[pos-1]]=rightt[pos];
				leftt[rightt[pos]]=leftt[pos-1];
				s.erase({leftt[pos-1],pos-1});
				s.erase({pos,rightt[pos]});
				s.insert({leftt[pos-1],rightt[pos]});
				rightt[pos]=-1;
				leftt[pos-1]=-1;
			}
			if(pos<(n-1) && rightt[pos+1]!=-1){
				rightt[leftt[pos]]=rightt[pos+1];
				leftt[rightt[pos+1]]=leftt[pos];
				s.erase({leftt[pos],pos});
				s.erase({pos+1,rightt[pos+1]});
				s.insert({leftt[pos],rightt[pos+1]});
				rightt[pos+1]=-1;
				leftt[pos]=-1;
			}
		}
	}
	else{
		pair<ll,ll>temp={pos,1000000000};
		auto it=s.lower_bound(temp);
		--it;
		if(it->first<=pos && pos<=it->second){
			ll st=it->first;
			ll en=it->second;
			s.erase(it);
			leftt[en]=-1;
			rightt[st]=-1;
			if(st!=pos){
				rightt[st]=pos-1;
				leftt[pos-1]=st;
				s.insert({st,pos-1});
			}
			if(en!=pos){
				leftt[en]=pos+1;
				rightt[pos+1]=en;
				s.insert({pos+1,en});
			}
		}
	}
	long long c=y[n-1];
	pair<long double,ll>p={0,-1};
	for(ll i=n-1;i>=0;i--){
		ll value=y[i];
		if(leftt[i]==-1){
			i=leftt[i];
			value=query1(1,0,n-1,i,rightt[i]);	
		} 
		p=max(p,{(long double)(c)/(long double)(value),i});
		c*=x[i];
		if(c>=1000000000) break;
	}
	ll ans=query(1,0,n-1,0,p.second);
	ll id=p.second,value=y[id];
	if(rightt[id]!=-1) value=query1(1,0,n-1,id,rightt[id]);
	return (ans*value)%MOD;
}

int updateY(int pos, int val) {
	update1(1,0,n-1,pos,val);
	y[pos]=val;
	long long c=y[n-1];
	pair<long double,ll>p={0,-1};
	for(ll i=n-1;i>=0;i--){
		ll value=y[i];
		if(leftt[i]==-1){
			i=leftt[i];
			value=query1(1,0,n-1,i,rightt[i]);	
		} 
		p=max(p,{(long double)(c)/(long double)(value),i});
		c*=x[i];
		if(c>=1000000000) break;
	}
	ll ans=query(1,0,n-1,0,p.second);
	ll id=p.second,value=y[id];
	if(rightt[id]!=-1) value=query1(1,0,n-1,id,rightt[id]);
	return (ans*value)%MOD;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:108:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  108 |  return (ans*val)%MOD;
      |                  ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:179:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  179 |  return (ans*value)%MOD;
      |                    ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:200:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  200 |  return (ans*value)%MOD;
      |                    ^
horses.cpp:191:16: warning: array subscript -1 is below array bounds of 'long long int [500005]' [-Warray-bounds]
  191 |    value=query1(1,0,n-1,i,rightt[i]);
      |          ~~~~~~^~~~~~~~~~~~~~~~~~~~~
horses.cpp:6:31: note: while referencing 'rightt'
    6 | long long y[500005],x[500005],rightt[500005],leftt[500005];
      |                               ^~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:99:14: warning: array subscript -1 is below array bounds of 'long long int [500005]' [-Warray-bounds]
   99 |    val=query1(1,0,n-1,i,rightt[i]);
      |        ~~~~~~^~~~~~~~~~~~~~~~~~~~~
horses.cpp:6:31: note: while referencing 'rightt'
    6 | long long y[500005],x[500005],rightt[500005],leftt[500005];
      |                               ^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:170:16: warning: array subscript -1 is below array bounds of 'long long int [500005]' [-Warray-bounds]
  170 |    value=query1(1,0,n-1,i,rightt[i]);
      |          ~~~~~~^~~~~~~~~~~~~~~~~~~~~
horses.cpp:6:31: note: while referencing 'rightt'
    6 | long long y[500005],x[500005],rightt[500005],leftt[500005];
      |                               ^~~~~~

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