Submission #438536

#	Time	Username	Problem	Language	Result	Execution time	Memory
438536		dutch	Horses (IOI15_horses)	C++17	17 / 100	217 ms	81128 KiB

horses

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

const int MOD = 1e9+7;

struct mint{
	ll v = 0; bool b = 0;
	mint(int V=0, bool B=0) : v(V) {};
	friend mint operator*(mint x, mint y){
		return mint((x.v * y.v) % MOD, x.b || y.b || x.v * y.v >= MOD);
	}
};

template<class T> struct SegmentTree{
	const T ID = {1, 0, 1, 0}; // product of X[i]s, best, suffix after best, Y[at best]
	T comb(T &x, T &y){
		mint z = x[2] * y[1];
		if(z.b || z.v > x[3].v) return {
			x[0] * y[0],
			x[0] * y[1],
			y[2],
			y[3]
		};
		else return {
			x[0] * y[0],
			x[1],
			x[2] * y[0],
			x[3]
		};
	}
	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]); }
	int operator()(){ return a[1][1].v; }
};

ll N, X[1<<19], Y[1<<19];
SegmentTree<array<mint, 4>> st;

int init(int n, int x[], int y[]){
	st.init(N=n);
	for(int i=0; i<n; ++i){
		X[i] = x[i], Y[i] = y[i];
		st[i] = st.a[0] = {X[i], X[i] * Y[i], 1, Y[i]};
	}
	return st();
}
 
int updateX(int i, int v){
	X[i] = v;
	st[i] = st.a[0] = {X[i], X[i] * Y[i], 1, Y[i]};
	return st();
}
 
int updateY(int i, int v){
	Y[i] = v;
	st[i] = st.a[0] = {X[i], X[i] * Y[i], 1, Y[i]};
	return st();
}

Compilation message (stderr)

horses.cpp: In constructor 'mint::mint(int, bool)':
horses.cpp:10:21: warning: unused parameter 'B' [-Wunused-parameter]
   10 |  mint(int V=0, bool B=0) : v(V) {};
      |                ~~~~~^~~
horses.cpp: In function 'mint operator*(mint, mint)':
horses.cpp:12:27: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   12 |   return mint((x.v * y.v) % MOD, x.b || y.b || x.v * y.v >= MOD);
      |               ~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:45:11: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   45 |  st.init(N=n);
      |          ~^~
horses.cpp:48:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   48 |   st[i] = st.a[0] = {X[i], X[i] * Y[i], 1, Y[i]};
      |                      ~~~^
horses.cpp:48:33: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   48 |   st[i] = st.a[0] = {X[i], X[i] * Y[i], 1, Y[i]};
      |                            ~~~~~^~~~~~
horses.cpp:48:47: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   48 |   st[i] = st.a[0] = {X[i], X[i] * Y[i], 1, Y[i]};
      |                                            ~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:55:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   55 |  st[i] = st.a[0] = {X[i], X[i] * Y[i], 1, Y[i]};
      |                     ~~~^
horses.cpp:55:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   55 |  st[i] = st.a[0] = {X[i], X[i] * Y[i], 1, Y[i]};
      |                           ~~~~~^~~~~~
horses.cpp:55:46: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   55 |  st[i] = st.a[0] = {X[i], X[i] * Y[i], 1, Y[i]};
      |                                           ~~~^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:61:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   61 |  st[i] = st.a[0] = {X[i], X[i] * Y[i], 1, Y[i]};
      |                     ~~~^
horses.cpp:61:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   61 |  st[i] = st.a[0] = {X[i], X[i] * Y[i], 1, Y[i]};
      |                           ~~~~~^~~~~~
horses.cpp:61:46: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   61 |  st[i] = st.a[0] = {X[i], X[i] * Y[i], 1, Y[i]};
      |                                           ~~~^
horses.cpp: In instantiation of 'int SegmentTree<T>::operator()() [with T = std::array<mint, 4>]':
horses.cpp:50:12:   required from here
horses.cpp:38:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   38 |  int operator()(){ return a[1][1].v; }
      |                           ~~~~~~~~^

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