Submission #140496

#	Time	Username	Problem	Language	Result	Execution time	Memory
140496		SirCeness	Horses (IOI15_horses)	C++14	17 / 100	1563 ms	29352 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000009
#define mod 1000000007
#define ppair(x); cerr << "(" << x.first << ", " << x.second << ")\n";
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define orta ((l+r)>>1)
using namespace std;
typedef long long ll;

double arr[500005];
ll arrmod[500005];
int st[4*500005];
double lazy[4*500005];
int n;
int x[500005];
int y[500005];

ll us(ll a, ll b){
	ll ans = 1;
	while (b){
		if (b & 1){
			ans *= a;
			ans %= mod;
		}
		a *= a;
		a %= mod;
		b >>= 1;
	}
	return ans;
}

ll inv(ll a){
	return us(a, mod-2);
}

void push(int node){
	lazy[node*2] += lazy[node];
	lazy[node*2+1] += lazy[node];
	lazy[node] = 0;
}

int get(int node){
	push(node);
	return st[node];
}

double getval(int node, int l, int r, int ind){
	if (l == r) return lazy[node] + arr[l];
	else {
		if (ind <= orta){
			return getval(node*2, l, orta, ind) + lazy[node];
		} else return getval(node*2+1, orta+1, r, ind) + lazy[node];
	}
}

void stc(int node, int l, int r){
	if (l == r){
		lazy[node] = 0;
		st[node] = l;
	} else {
		int m = orta;
		stc(node*2, l, m);
		stc(node*2+1, m+1, r);
		double val1 = getval(1, 0, n-1, st[node*2]);
		double val2 = getval(1, 0, n-1, st[node*2+1]);
		st[node] = (val1 > val2) ? st[node*2] : st[node*2+1];
		lazy[node] = 0;
	}
}

int stq(int node, int l, int r, int sl, int sr){
	if (inside) return get(node);
	else if (outside) return 0;
	else {
		push(node);
		int m = orta;
		int i1 = stq(node*2, l, m, sl, sr);
		int i2 = stq(node*2+1, m+1, r, sl, sr);
		return getval(1, 0, n-1, i1) > getval(1, 0, n-1, i2) ? i1 : i2;
	}
}

void stu(int node, int l, int r, int ind, double val){
	if (l == r) arr[l] += val;
	else {
		push(node);
		int m = orta;
		if (ind <= m) stu(node*2, l, m, ind, val);
		else stu(node*2+1, m+1, r, ind, val);
		
		double val1 = getval(1, 0, n-1, st[node*2]);
		double val2 = getval(1, 0, n-1, st[node*2+1]);
		st[node] = (val1 > val2) ? st[node*2] : st[node*2+1];
	}
}

void stul(int node, int l, int r, int sl, int sr, double val){
	if (inside) lazy[node] += val;
	else if (outside) return;
	else {
		int m = orta;
		push(node);
		stul(node*2, l, m, sl, sr, val);
		stul(node*2+1, m+1, r, sl, sr, val);
		
		double val1 = getval(1, 0, n-1, st[node*2]);
		double val2 = getval(1, 0, n-1, st[node*2+1]);
		st[node] = (val1 > val2) ? st[node*2] : st[node*2+1];
	}
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 0; i < n; i++) x[i] = X[i];
	for (int i = 0; i < n; i++) y[i] = Y[i];
	double sum = 0;
	ll summod = 1;
	for (int i = 0; i < n; i++){
		sum += log2(X[i]);
		arr[i] = sum + log2(Y[i]);
		
		summod *= X[i];
		summod %= mod;
		arrmod[i] = (summod*Y[i])%mod;
		
	}
	
	//prarr(arr, n);
	
	stc(1, 0, n-1);
	
	//for (int i = 0; i < 3; i++) cout << getval(1, 0, n-1, i) << " "; cout << endl;
	
	return arrmod[stq(1, 0, n-1, 0, n-1)];
}

int updateX(int pos, int val){
	//stul(1, 0, n-1, 0, pos, log2(val)-log2(x[pos]));
	for (int i = 0; i < pos; i++){
		arr[i] += log2(val)-log2(x[pos]);
	}
	for (int i = 0; i < pos; i++){
		arrmod[i] *= inv(x[pos]);
		arrmod[i] %= mod;
		arrmod[i] *= (ll)val;
		arrmod[i] %= mod;
	}
	x[pos] = val;
	int maxi = 0;
	double maxx = 0;
	for (int i = 0; i < n; i++) {
		if (arr[i] > maxx) maxi = i, maxx = arr[i];
	}
	return arrmod[maxi];
}

int updateY(int pos, int val) {
	//cout << "update " << pos << " -> " << log2(val) - log2(y[pos]) << endl;
	stu(1, 0, n-1, pos, log2(val) - log2(y[pos]));
	//prarr(arr, 3);
	//for (int i = 0; i < 3; i++) cout << getval(1, 0, n-1, i) << " "; cout << endl;
	arrmod[pos] *= inv(y[pos]);
	arrmod[pos] %= mod;
	arrmod[pos] *= val;
	arrmod[pos] %= mod;
	y[pos] = val;
	return arrmod[stq(1, 0, n-1, 0, n-1)];
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:143:38: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return arrmod[stq(1, 0, n-1, 0, n-1)];
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:163:20: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return arrmod[maxi];
         ~~~~~~~~~~~^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:176:38: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return arrmod[stq(1, 0, n-1, 0, n-1)];
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^

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