Submission #847383

#	Time	Username	Problem	Language	Result	Execution time	Memory
847383		PenguinsAreCute	Horses (IOI15_horses)	C++17	100 / 100	254 ms	41296 KiB

horses

// As usual, don't miss a chance to make your code 69 lines...
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=b-1;i>=a;i--)
#define SZ 500069
#define MOD 1000000007
int n, v[SZ<<1], x[SZ];
void initTree(int Y[]) {
	REP(i,n,(n<<1)) v[i]=Y[i-n];
	RREP(i,1,n) v[i]=max(v[i<<1],v[i<<1 | 1]);
}
void up(int pos, int val) {for(v[pos+=n]=val;pos>1;pos>>=1) v[pos>>1]=max(v[pos],v[pos^1]);}
int qry(int l, int r) {
	int res=0;
	for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
		if(l&1) res=max(res,v[l++]);
		if(r&1) res=max(res,v[--r]);
	}
	return res;
}
set<int> s;
int prod=1;
int mul(int a, int b) {return (1LL*a*b)%MOD;}
int exp(int a, int b) {
    int ans=1, basepow=a;
    REP(i,0,30) {
        if((1<<i)&b) ans=mul(ans,basepow);
        basepow=mul(basepow,basepow);
    }
    return ans;
}
int compute() {
	auto it=s.end(); it--;
	long long inProd=1; long double ans=0; int actAns=0;
	do {
		auto nd=it--;
		int qAns=qry(*it,*nd);
		if(qAns/(long double)inProd > ans) {
			ans = qAns/(long double)inProd;
			actAns=mul(prod,mul(qAns,exp(inProd,MOD-2)));
		}
		inProd *= x[*it];
	} while(it!=s.begin()&&inProd<1000000000);
	return actAns;
}
int init(int N, int X[], int Y[]) {
	n=N;
	initTree(Y);
	REP(i,0,N) {
		if(X[i]!=1) s.insert(i);
		x[i]=X[i]; prod=mul(prod,X[i]);
	}
	s.insert(N); s.insert(0);
	return compute();
}
int updateX(int pos, int val) {	
	if(val==1 && pos) s.erase(pos);
	else s.insert(pos);
	prod=mul(prod,mul(val,exp(x[pos],MOD-2)));
	x[pos]=val;
	return compute();
}
int updateY(int pos, int val) {
	up(pos,val);
	return compute();
}

Compilation message (stderr)

horses.cpp: In function 'int mul(int, int)':
horses.cpp:26:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   26 | int mul(int a, int b) {return (1LL*a*b)%MOD;}
      |                                        ^
horses.cpp: In function 'int compute()':
horses.cpp:43:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   43 |    actAns=mul(prod,mul(qAns,exp(inProd,MOD-2)));
      |                                 ^~~~~~

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