제출 #310356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
310356		tengiz05	말 (IOI15_horses)	C++17	100 / 100	426 ms	88696 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
int n;
const int NN = 1e6+5;
const ll mod = 1e9+7;
ll a[NN];
ll b[NN];
//=============================================
ll binpow(ll p, ll q){
	if(q == 0)return 1ll;
	ll temp = binpow(p, q/2);
	temp *= temp;
	temp %= mod;
	if(q%2==1)temp *= p;
	return temp%mod;
}ll inver(ll p){
	return binpow(p, mod-2);
}//===============================================

struct Node {
	ld sum;
	ll mul;
};
Node neutral = {0., 1ll};
int sz;
vector<Node> t;
vector<Node> ans;
Node combine(Node f, Node s){
	return {f.sum+s.sum, (f.mul*s.mul)%mod};
}
Node mx(Node f, Node s){
	if(f.sum > s.sum)return f;
	else return s;
}
void build(){
	sz=1;
	while(sz<n)sz<<=1;
	t.assign(sz*2, neutral);
	ans.assign(sz*2, neutral);
	for(int i=0;i<n;i++){
		t[i+sz].sum = log2(a[i]);
		t[i+sz].mul = a[i];
	}for(int i=1;i<sz;i++){
		t[i+sz].sum += t[i+sz-1].sum;
		t[i+sz].mul *= t[i+sz-1].mul;t[i+sz].mul%=mod;
	}for(int i=0;i<sz;i++){
		ans[i+sz].sum = t[i+sz].sum+log2(b[i]);
		ans[i+sz].mul =(t[i+sz].mul*b[i])%mod;
	}for(int i=sz-1;i>0;i--){
		ans[i] = mx(ans[i*2], ans[i*2+1]);
	}
}
Node getpref(int i){
	ld ansd = 0.;
	ll ansl = 1;
	for(i+=sz; i>0; i>>=1){
		ansd += t[i].sum;
		ansl *= t[i].mul;ansl%=mod;
	}return {ansd, ansl};
}
void push(int L, int R, int node){
	if(R-L == 1)return;
	t[node*2] = combine(t[node], t[node*2]);
	t[node*2+1]=combine(t[node], t[node*2+1]);
	ans[node*2] = combine(ans[node*2], t[node]);
	ans[node*2+1]=combine(ans[node*2+1], t[node]);
	
	t[node] = neutral;
	ans[node] = mx(ans[node*2], ans[node*2+1]);
}
void modifyX(int l, int r, int L, int R, Node val, int node){
	if(L >= r || R <= l)return;
	push(L, R, node);
	if(L >= l && R <= r){
		t[node] = combine(t[node], val);
		ans[node]=combine(ans[node], val);
		return;
	}int mid = (L+R)/2;
	modifyX(l, r, L, mid, val, node*2);
	modifyX(l, r, mid, R, val, node*2+1);
	ans[node] = mx(ans[node*2], ans[node*2+1]);
}
void modifyY(int pos, int L, int R, Node val, int node){
	if(R-L == 1){
		ans[node] = val;
		return;
	}int mid = (L+R)/2;
	push(L, R, node);
	if(mid <= pos){
		modifyY(pos, mid, R, val, node*2+1);
	}else {
		modifyY(pos, L, mid, val, node*2);
	}ans[node] = mx(ans[node*2], ans[node*2+1]);
}//===============================================


int init(int N, int X[], int Y[]) {
	n = N;
	for(int i=0;i<n;i++)a[i] = X[i];
	for(int i=0;i<n;i++)b[i] = Y[i];
	build();
	return ans[1].mul;
}

int updateX(int pos, int val) {
//	Node X = getpref(pos);
	modifyX(pos, sz, 0, sz, {log2(val)-log2(a[pos]), ((val*inver(a[pos]))%mod)}, 1);
	a[pos] = val;
	return ans[1].mul;
}

int updateY(int pos, int val) {
	Node X = getpref(pos);
	modifyY(pos, 0, sz, {X.sum+log2(val), (X.mul*val)%mod}, 1);
	b[pos] = val;
	return ans[1].mul;
}

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

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:105:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  105 |  return ans[1].mul;
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:112:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  112 |  return ans[1].mul;
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:119:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  119 |  return ans[1].mul;

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