Submission #140481

#	Time	Username	Problem	Language	Result	Execution time	Memory
140481		SirCeness	Horses (IOI15_horses)	C++14	17 / 100	49 ms	20228 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];
int n;

void stc(int node, int l, int r){
	if (l == r) st[node] = l;
	else {
		int m = orta;
		stc(node*2, l, m);
		stc(node*2+1, m+1, r);
		st[node] = (arr[st[node*2]] > arr[st[node*2+1]]) ? st[node*2] : st[node*2+1];
	}
}

double stq(int node, int l, int r, int sl, int sr){
	if (inside) return st[node];
	else if (outside) return 0;
	else {
		int m = orta;
		int i1 = stq(node*2, l, m, sl, sr);
		int i2 = stq(node*2+1, m+1, r, sl, sr);
		return arr[i1] > arr[i2] ? i1 : i2;
	}
}

int init(int N, int X[], int Y[]) {
	n = N;
	
	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);
	
	int i = stq(1, 0, n-1, 0, n-1);
	
	return arrmod[i];
}

int updateX(int pos, int val){
	
	return 0;
}

int updateY(int pos, int val) {
	return 0;
}

Compilation message (stderr)

horses.cpp: In function 'double stq(int, int, int, int, int)':
horses.cpp:39:15: warning: conversion to 'int' from 'double' may alter its value [-Wfloat-conversion]
   int i1 = stq(node*2, l, m, sl, sr);
            ~~~^~~~~~~~~~~~~~~~~~~~~~
horses.cpp:40:15: warning: conversion to 'int' from 'double' may alter its value [-Wfloat-conversion]
   int i2 = stq(node*2+1, m+1, r, sl, sr);
            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:64:13: warning: conversion to 'int' from 'double' may alter its value [-Wfloat-conversion]
  int i = stq(1, 0, n-1, 0, n-1);
          ~~~^~~~~~~~~~~~~~~~~~~
horses.cpp:66:17: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return arrmod[i];
         ~~~~~~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:69:17: warning: unused parameter 'pos' [-Wunused-parameter]
 int updateX(int pos, int val){
                 ^~~
horses.cpp:69:26: warning: unused parameter 'val' [-Wunused-parameter]
 int updateX(int pos, int val){
                          ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:74:17: warning: unused parameter 'pos' [-Wunused-parameter]
 int updateY(int pos, int val) {
                 ^~~
horses.cpp:74:26: warning: unused parameter 'val' [-Wunused-parameter]
 int updateY(int pos, int val) {
                          ^~~

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