Submission #310499

#	Time	Username	Problem	Language	Result	Execution time	Memory
310499		amunduzbaev	Horses (IOI15_horses)	C++14	100 / 100	443 ms	79608 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;
}

struct Node {
	ld sum;
	ll answ;
};
Node neutral = {0., 1ll};
int sz;
vector<Node> t;
vector<Node> ans;
Node combine(Node f, Node s){
	return {f.sum+s.sum, (f.answ*s.answ)%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].answ = a[i];
	}for(int i=1;i<sz;i++){
		t[i+sz].sum += t[i+sz-1].sum;
		t[i+sz].answ *= t[i+sz-1].answ;t[i+sz].answ%=mod;
	}for(int i=0;i<sz;i++){
		ans[i+sz].sum = t[i+sz].sum+log2(b[i]);
		ans[i+sz].answ =(t[i+sz].answ*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].answ;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 lx, int rx, Node val, int node){
	if(lx >= r || rx <= l)return;
	push(lx, rx, node);
	if(lx >= l && rx <= r){
		t[node] = combine(t[node], val);
		ans[node]=combine(ans[node], val);
		return;
	}int mid = (lx+rx)/2;
	modifyX(l, r, lx, mid, val, node*2);
	modifyX(l, r, mid, rx, val, node*2+1);
	ans[node] = mx(ans[node*2], ans[node*2+1]);
}
void modifyY(int pos, int lx, int rx, Node val, int node){
	if(rx-lx == 1){
		ans[node] = val;
		return;
	}int mid = (lx+rx)/2;
	push(lx, rx, node);
	if(mid <= pos){
		modifyY(pos, mid, rx, val, node*2+1);
	}else {
		modifyY(pos, lx, 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].answ;
}

int updateX(int pos, int val) {
	modifyX(pos, sz, 0, sz, {log2(val)-log2(a[pos]), ((val*binpow(a[pos],mod-2))%mod)}, 1);
	a[pos] = val;
	return ans[1].answ;
}

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

Compilation message (stderr)

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

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