Submission #158599

#	Time	Username	Problem	Language	Result	Execution time	Memory
158599		oolimry	Horses (IOI15_horses)	C++14	17 / 100	1583 ms	91164 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;
		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;
		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;

Segtree seg;
long long answer(){
	int pos = seg.query();
	long long value = 1;
	for(int i = 0;i <= pos;i++){
		value *= x[i];
		value %= mod;
	}
	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]);
	}
	seg.create(n);
	
	return answer();
}

int updateX(int pos, int val) {	
	x[pos] = val;
	double oln = lnx[pos];
	lnx[pos] = (double)log2((double)x[pos]);
	oln = lnx[pos] - oln;
	seg.update(pos,n,oln);
	return answer();
}

int updateY(int pos, int val) {
	y[pos] = val;
	double oln = lny[pos];
	lny[pos] = (double)log2((double)y[pos]);
	oln = lnx[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:89: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:94:22: warning: conversion to 'double' from 'long double' may alter its value [-Wfloat-conversion]
  double oln = lnx[pos];
               ~~~~~~~^
horses.cpp:96:17: warning: conversion to 'double' from 'long double' may alter its value [-Wfloat-conversion]
  oln = lnx[pos] - oln;
        ~~~~~~~~~^~~~~
horses.cpp:98: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:103:22: warning: conversion to 'double' from 'long double' may alter its value [-Wfloat-conversion]
  double oln = lny[pos];
               ~~~~~~~^
horses.cpp:105:17: warning: conversion to 'double' from 'long double' may alter its value [-Wfloat-conversion]
  oln = lnx[pos] - oln;
        ~~~~~~~~~^~~~~
horses.cpp:107:15: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return answer();
         ~~~~~~^~

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