Submission #437678

#	Time	Username	Problem	Language	Result	Execution time	Memory
437678		dutch	Horses (IOI15_horses)	C++17	17 / 100	758 ms	53584 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 % MOD) * (v % MOD)) % 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 cnt = 0, j = n;
	s.insert(0);
	for(int i : s){
		if(++cnt > 32) break;
		a.push_back({-i, y(-i, j-1)});
		j = -i;
	}
	reverse(a.begin(), a.end());
	array<ll, 3> c = {1, 0, 0};
	for(auto &i : a){
		c[0] *= x(i[0], i[0]);
		if(c[0] * i[1] > c[2]){
			c[2] = c[0] * i[1];
			c[1] = ((x(0, i[0]) % MOD) * i[1]) % MOD;
		}
	}
	return c[1];
}

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:48:12: warning: conversion from 'std::array<long long int, 3>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   48 |  return c[1];
      |            ^

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