Submission #158605

#	Time	Username	Problem	Language	Result	Execution time	Memory
158605		oolimry	Horses (IOI15_horses)	C++14	100 / 100	423 ms	112624 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
long long x[500005];
long long y[500005];

long double lnx[500005];
long double lny[500005];

typedef pair<long double, int> ii;
class Segtree{
public:
	int n;
	vector<ii> tree;
	vector<long double> lazy;
	void create(int nn){
		n = nn;
		for(int i = 0;i < 2*n+5;i++){
			tree.push_back(ii(0.0,0));
			lazy.push_back(0.0);
		}
		long double acc = 0.0;
		for(int i = 0;i < n;i++){
			acc += lnx[i];
			tree[i+n] = ii(acc+lny[i],i);
		}
		for(int i = n-1;i >= 1;i--){
			tree[i] = max(tree[i<<1],tree[i<<1|1]);
		}
	}
	
	int query(){
		return tree[1].second;
	}
	
	void update(int l, int r, long double v){
		int ll = l + n; int rr = r + n - 1;
		for(l += n, r += n;l < r;l >>= 1, r >>= 1){
			if(l&1){
				lazy[l] += v;
				tree[l].first += v;
				l++;
			}
			if(r&1){
				r--;
				lazy[r] += v;
				tree[r].first += v;
			}
		}
		while(ll > 1){
			ll >>= 1;
			ii x = max(tree[ll<<1],tree[ll<<1|1]);
			tree[ll] = ii(x.first + lazy[ll], x.second);
		}
		while(rr > 1){
			rr >>= 1;
			ii x = max(tree[rr<<1],tree[rr<<1|1]);
			tree[rr] = ii(x.first + lazy[rr], x.second);
		}
	}
	
};
int n;
long long tree[1000005];
long long queryd(int l, int r){
	long long ans = 1;
	for(l += n, r += n;l < r;l >>= 1, r >>= 1){
		if(l&1){
			ans *= tree[l];
			ans %= mod;
			l++;
		}
		if(r&1){
			r--;
			ans *= tree[r];
			ans %= mod;
		}
	}
	return ans;
}
Segtree seg;
long long answer(){
	int pos = seg.query();
	long long value =  queryd(0,pos+1);
	value *= y[pos];
	value %= mod;
	return value;
}
int init(int N, int X[], int Y[]) {
	n = N;
	for(int i = 0;i < N;i++){
		x[i] = X[i];
		y[i] = Y[i];
		lnx[i] = (double)log2((double)X[i]);
		lny[i] = (double)log2((double)Y[i]);
		//printf("%f %f\n",lnx[i],lny[i]);
		tree[i+n] = x[i];
	}
	
	for(int i = n-1;i >= 1;i--){
		tree[i] = tree[i<<1] * tree[i<<1|1];
		tree[i] %= mod;
	}
	seg.create(n);
	
	return answer();
}

int updateX(int pos, int val) {	
	x[pos] = val;
	long double oln = lnx[pos];
	lnx[pos] = (double)log2((double)x[pos]);
	oln = lnx[pos] - oln;
	seg.update(pos,n,oln);
	
	tree[pos+n] = val;
	int i = (pos + n) >> 1;
	while(i > 0){
		tree[i] = tree[i<<1] * tree[i<<1|1];
		tree[i] %= mod;
		i >>= 1;
	}
	return answer();
}

int updateY(int pos, int val) {
	y[pos] = val;
	long double oln = lny[pos];
	lny[pos] = (double)log2((double)y[pos]);
	oln = lny[pos] - oln;
	seg.update(pos,pos+1,oln);
	return answer();
}

Compilation message (stderr)

horses.cpp: In member function 'void Segtree::update(int, int, long double)':
horses.cpp:53:7: warning: declaration of 'x' shadows a global declaration [-Wshadow]
    ii x = max(tree[ll<<1],tree[ll<<1|1]);
       ^
horses.cpp:5:11: note: shadowed declaration is here
 long long x[500005];
           ^
horses.cpp:58:7: warning: declaration of 'x' shadows a global declaration [-Wshadow]
    ii x = max(tree[rr<<1],tree[rr<<1|1]);
       ^
horses.cpp:5:11: note: shadowed declaration is here
 long long x[500005];
           ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:107:15: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return answer();
         ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:124:15: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return answer();
         ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:133:15: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return answer();
         ~~~~~~^~

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