Submission #408740

#	Time	Username	Problem	Language	Result	Execution time	Memory
408740		pliam	Horses (IOI15_horses)	C++14	100 / 100	765 ms	46128 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF (ll)1000000005//biggest than max Y
#define MOD (ll)1000000007//modulo for evaluation
#define MAXN 500005

ll x[MAXN],y[MAXN];
int mxst[4*MAXN];
pair<ll,ll> prst[4*MAXN];//(real,mod);
int n;

ll pr(ll a,ll b){
	return ((a*b)>=INF)?INF:(a*b);
}

ll prmod(ll a,ll b){
	return (a*b)%MOD;
}

pair<ll,ll> pr(pair<ll,ll> a,pair<ll,ll> b){
	return {pr(a.first,b.first),prmod(a.second,b.second)};
}

void prbuild(int v=1,int start=0,int end=n-1){
	if(start==end){
		prst[v]={x[start],x[start]};
		return;
	}
	int mid=(start+end)/2;
	prbuild(2*v,start,mid);
	prbuild(2*v+1,mid+1,end);
	prst[v]=pr(prst[2*v],prst[2*v+1]);
}

void prupdate(int pos,int v=1,int start=0,int end=n-1){
	if(start==end){
		prst[v]={x[start],x[start]};
		return;
	}
	int mid=(start+end)/2;
	if(pos<=mid){
		prupdate(pos,2*v,start,mid);
	}else{
		prupdate(pos,2*v+1,mid+1,end);
	}
	prst[v]=pr(prst[2*v],prst[2*v+1]);
}

pair<ll,ll> prquery(int from,int to,int v=1,int start=0,int end=n-1){
	if(start==from&&end==to){
		return prst[v];
	}
	int mid=(start+end)/2;
	if(to<=mid){
		return prquery(from,to,2*v,start,mid);
	}else if(from>mid){
		return prquery(from,to,2*v+1,mid+1,end);
	}else{
		return pr(prquery(from,mid,2*v,start,mid),prquery(mid+1,to,2*v+1,mid+1,end));
	}
}

int mx(int i,int j){//i<j
	return (y[i]>pr(prquery(i+1,j).first,y[j]))?i:j;
}

void mxbuild(int v=1,int start=0,int end=n-1){
	if(start==end){
		mxst[v]=start;
		return;
	}
	int mid=(start+end)/2;
	mxbuild(2*v,start,mid);
	mxbuild(2*v+1,mid+1,end);
	mxst[v]=mx(mxst[2*v],mxst[2*v+1]);
}

void mxupdate(int pos,int v=1,int start=0,int end=n-1){
	if(start==end){
		mxst[v]=start;
		return;
	}
	int mid=(start+end)/2;
	if(pos<=mid){
		mxupdate(pos,2*v,start,mid);
	}else{
		mxupdate(pos,2*v+1,mid+1,end);
	}
	mxst[v]=mx(mxst[2*v],mxst[2*v+1]);
}

int evaluate(){
	int i=mxst[1];
	return prmod(prquery(0,i).second,y[i]);
}

int init(int N, int X[], int Y[]) {
	n=N;
	for(int i=0;i<n;i++){
		x[i]=X[i];
		y[i]=Y[i];
	}
	prbuild();
	mxbuild();
	return evaluate();
}

int updateX(int pos, int val) {	
	x[pos]=val;
	prupdate(pos);
	mxupdate(pos);
	return evaluate();
}

int updateY(int pos, int val) {
	y[pos]=val;
	mxupdate(pos);
	return evaluate();
}

Compilation message (stderr)

horses.cpp: In function 'int evaluate()':
horses.cpp:96:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   96 |  return prmod(prquery(0,i).second,y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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