Submission #411948

#	Time	Username	Problem	Language	Result	Execution time	Memory
411948		nxteru	Horses (IOI15_horses)	C++14	100 / 100	813 ms	65476 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define M 1000000007LL
struct SEG1{
	ll seg[1<<20];
	SEG1(void){
		for(int i=0;i<1<<20;i++)seg[i]=1;
	}
	void update(int a,ll x){
		a+=(1<<19)-1;
		seg[a]=x%M;
		while(a>0){
			a=(a-1)/2;
			seg[a]=seg[a*2+1]*seg[a*2+2]%M;
		}
	}
	ll query(int a,int b,int l=0,int r=(1<<19)-1,int k=0){
		if(r<a||b<l)return 1;
		if(a<=l&&r<=b)return seg[k];
		return query(a,b,l,(l+r-1)/2,k*2+1)*query(a,b,(l+r+1)/2,r,k*2+2)%M;
	}
}seg1;

struct SEG2{
	ll seg[1<<20];
	SEG2(void){
		for(int i=0;i<1<<20;i++)seg[i]=0;
	}
	void update(int a,ll x){
		a+=(1<<19)-1;
		seg[a]=x;
		while(a>0){
			a=(a-1)/2;
			seg[a]=max(seg[a*2+1],seg[a*2+2]);
		}
	}
	ll query(int a,int b,int l=0,int r=(1<<19)-1,int k=0){
		if(r<a||b<l)return 0;
		if(a<=l&&r<=b)return seg[k];
		return max(query(a,b,l,(l+r-1)/2,k*2+1),query(a,b,(l+r+1)/2,r,k*2+2));
	}
}seg2;

ll n,x[500005],y[500005];
set<ll>p;

int solve(void){
	auto it=p.find(n);
	vector<ll>a,b,c;
	int la=n;
	ll s=1;
	while(1){
		it--;
		int v=*it;
		a.push_back(v);
		b.push_back(s);
		c.push_back(seg2.query(v,la-1));
		if(it==p.begin()||s*x[v]>=1000000000)break;
		s*=x[v];
		la=v;
	}
	pair<ll,int>ma=make_pair(-1,-1);
	for(int i=0;i<a.size();i++){
		ma=max(ma,make_pair(s/b[i]*c[i],i));
	}
	return seg1.query(0,a[ma.second])*c[ma.second]%M;
}

int init(int N,int X[],int Y[]) {
	n=N;
	p.insert(n);
	for(int i=0;i<n;i++){
		x[i]=X[i];
		seg1.update(i,x[i]);
		if(i==0||x[i]>1)p.insert(i);
		y[i]=Y[i];
		seg2.update(i,y[i]);
	}
	return solve();
}

int updateX(int pos,int val) {	
	x[pos]=val;
	seg1.update(pos,val);
	if(x[pos]>1)p.insert(pos);
	else if(pos!=0)p.erase(pos);
	return solve();
}

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

Compilation message (stderr)

horses.cpp: In function 'int solve()':
horses.cpp:52:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   52 |  int la=n;
      |         ^
horses.cpp:56:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   56 |   int v=*it;
      |         ^~~
horses.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0;i<a.size();i++){
      |              ~^~~~~~~~~
horses.cpp:68:34: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   68 |  return seg1.query(0,a[ma.second])*c[ma.second]%M;
      |                                  ^
horses.cpp:68:48: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   68 |  return seg1.query(0,a[ma.second])*c[ma.second]%M;
      |                                                ^

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