제출 #438539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
438539		dutch	말 (IOI15_horses)	C++17	100 / 100	373 ms	88616 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), b(B) {};
	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; mint 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();
}

컴파일 시 표준 에러 (stderr) 메시지

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: 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: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23