Submission #437683

#	Time	Username	Problem	Language	Result	Execution time	Memory
437683		dutch	Horses (IOI15_horses)	C++17	100 / 100	880 ms	53500 KiB

horses

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include "horses.h"

const int MOD = 1e9+7;

template<class T> struct SegmentTree{
	function<T(T, T)> comb = [](T u, T v){ return (u * v) % MOD; };
	T ID = 1; int n = 1, i; vector<T> a;
	void init(int N){ while((n+=n) < N); a.assign(2*n, ID); }
	SegmentTree& operator[](int j){ i=j+n; return *this; }
	void operator=(T v){
		for(a[i]=v; i/=2; ) a[i] = comb(a[2*i], a[2*i+1]); }
	T operator()(int l, int r){
		T lx = ID, rx = ID;
		for(l+=n, r+=n+1; l<r; l/=2, r/=2){
			if(l & 1) lx = comb(lx, a[l++]);
			if(r & 1) rx = comb(a[--r], rx);
		}
		return comb(lx, rx);
	}
};

int n;
SegmentTree<ll> x;
SegmentTree<int> y;
set<int> s;

int find(){
	vector<array<int, 2>> a;
	int j = n; ll p = 1, res = 0;
	s.insert(0);
	for(int i : s){
		i = -i;
		a.push_back({i, y(i, j-1)});
		j = i;
		if((p *= x(i, i)) > (ll)1e9) break;
	}
	reverse(a.begin(), a.end());
	double pre = 1, cur = 0;
	for(auto &i : a){
		pre *= x(i[0], i[0]);
		if(pre * i[1] > cur){
			cur = pre * i[1];
			res = ((x(0, i[0]) % MOD) * i[1]) % MOD;
		}
	}
	return (res + MOD) % MOD;
}

int init(int N, int X[], int Y[]){
	x.init(n=N); y.init(n);
	y.ID = -1; y.comb = [](int u, int v){ return max(u, v); };
	for(int i=0; i<n; ++i){
		y[i] = Y[i]; x[i] = X[i];
		if(X[i] > 1) s.insert(-i);
	}
	return find();
}

int updateX(int i, int v){
	auto f = s.find(-i);
	if(v < 2 && f != s.end()) s.erase(f);
	if(v > 1) s.insert(-i);
	x[i] = v;
	return find();
}

int updateY(int i, int v){
	y[i] = v;
	return find();
}

Compilation message (stderr)

horses.cpp: In function 'int find()':
horses.cpp:43:22: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   43 |   pre *= x(i[0], i[0]);
      |                      ^
horses.cpp:49:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   49 |  return (res + MOD) % MOD;
      |         ~~~~~~~~~~~~^~~~~

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