Submission #210910

#	Time	Username	Problem	Language	Result	Execution time	Memory
210910		autumn_eel	Horses (IOI15_horses)	C++14	37 / 100	426 ms	48120 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

const int MOD=1000000007;

ll ppow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}

struct BIT{
	vector<ll>bit;
	BIT(){}
	BIT(int n){
		n=n+10;
		bit=vector<ll>(n,1);
	}
	void add(int k,ll x){
		k++;
		while(k<bit.size()){
			(bit[k]*=x)%=MOD;
			k+=k&-k;
		}
	}
	ll sum(int k){//[0,k)
		ll res=1;
		while(k){
			(res*=bit[k])%=MOD;
			k-=k&-k;
		}
		return res;
	}
}bit;

struct Segtree{
	int N;
	vector<int>dat;
	Segtree(){}
	Segtree(int n){
		N=1;while(N<n)N<<=1;
		dat=vector<int>(2*N);
	}
	void update(int k,int x){
		k+=N;dat[k]=x;
		while(k>1){
			k>>=1;
			dat[k]=max(dat[k*2],dat[k*2+1]);
		}
	}
	int query(int l,int r){
		int res=0;
		for(l+=N,r+=N;l<r;l>>=1,r>>=1){
			if(l&1)res=max(res,dat[l++]);
			if(r&1)res=max(res,dat[--r]);
		}
		return res;
	}
}seg;

int n;
ll x[600000],y[600000];
set<int>se;


ll calc(){
	if(se.empty())return seg.query(0,n)%MOD;
	ll res=0;
	ll M=1;
	auto s=--se.end();
	while(1){
		M*=x[*s];
		if(M>1e9||s==se.begin())break;
		s--;
	}
	__int128 Max=0,cur=1;
	for(auto it=s;it!=se.end();it++){
		cur*=x[*it];
		ll d=seg.query(*it,(it==--se.end()?n:*next(it)));
		assert(log2((ll)cur)+log2((ll)d)<=100);
		Max=max(Max,cur*d);
	}
	Max%=MOD;
	Max*=bit.sum(*s);
	return Max%MOD;
}

int init(int N, int X[], int Y[]) {
	n=N;
	bit=BIT(n);seg=Segtree(n);
	rep(i,n){
		x[i]=X[i],y[i]=Y[i];
		bit.add(i,x[i]);
		seg.update(i,y[i]);
		if(x[i]>1)se.insert(i);
	}
	return (int)calc();
}

int updateX(int pos, int val) {
	bit.add(pos,ppow(x[pos],MOD-2)*val%MOD);
	if(val==1){
		se.erase(pos);
	}
	else{
		se.insert(pos);
	}
	x[pos]=val;
	return (int)calc();
}

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

Compilation message (stderr)

horses.cpp: In member function 'void BIT::add(int, ll)':
horses.cpp:28:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(k<bit.size()){
         ~^~~~~~~~~~~
horses.cpp: In function 'll calc()':
horses.cpp:80:8: warning: conversion to 'double' from 'll {aka long long int}' may alter its value [-Wconversion]
   if(M>1e9||s==se.begin())break;
        ^~~
horses.cpp:92:12: warning: conversion to 'll {aka long long int}' from '__int128' may alter its value [-Wconversion]
  return Max%MOD;
         ~~~^~~~
horses.cpp:75:5: warning: unused variable 'res' [-Wunused-variable]
  ll res=0;
     ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:101:19: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   seg.update(i,y[i]);
                ~~~^

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