oj.uz

Submission #83066

# Submission time Handle Problem Language Result Execution time Memory
83066 2018-11-04T15:55:32 Z arman_ferdous Horses (IOI15_horses) C++17
0 / 100
 1500 ms 17416 KB 
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;

typedef long long ll;
const int N = 5e5+10;
const int K = 710;
const int MOD = 1e9+7;

int n, CNT;
double x[N], y[N];

struct Block{
	ll mul; int idx;
	double full, mx, sum[750];
}blc[750];

void updateBlock(int p) {
	int L = p * K, R = min(L + K - 1, n - 1);
	if(L > R) return;

	blc[p].mul = x[L];
	blc[p].idx = 0;
	blc[p].full = log(x[L]);

	blc[p].sum[0] = log(x[L]) + log(y[L]);
	
	blc[p].mx = blc[p].sum[0];
	for(int i = L+1; i <= R; i++) {
		blc[p].mul = blc[p].mul * (ll)x[i] % MOD;
		blc[p].full += log(x[i]);
		blc[p].sum[i - L] = blc[p].sum[i - L - 1] + log(x[i]) + log(y[i]) - log(y[i - 1]);
		if(blc[p].sum[i - L] > blc[p].mx)
			blc[p].idx = i - L, blc[p].mx = blc[p].sum[i - L];
	}
}

ll solve() {
	int idx, BlockNUM;
	double mx = 0, sum = 0;
	for(int i = 0; i <= CNT; i++) {
		if(sum + blc[i].sum[blc[i].idx] > mx) {
			mx = sum + blc[i].sum[blc[i].idx];
			BlockNUM = i; idx = blc[i].idx;
		} sum += blc[i].full;
	}
	ll ret = 1;
	for(int i = 0; i < BlockNUM; i++) 
		ret = ret * blc[i].mul % MOD;
	for(int i = 0, j = BlockNUM * K; i <= idx; i++, j++) {
		ret = ret * (ll)x[j] % MOD;
		if(i == idx) ret = ret * (ll)y[j] % MOD;
	}
	return ret;
}

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];

	// K = sqrt(n) + 1;
	CNT = (n - 1) / K;
	for(int i = 0; i <= CNT; i++) updateBlock(i);
	return solve();
}

int updateX(int pos, int val) {
	x[pos] = val;
	int BlockNUM = pos / K;
	updateBlock(BlockNUM);
	return solve();
}

int updateY(int pos, int val) {
	y[pos] = val;
	int BlockNUM = pos / K;
	updateBlock(BlockNUM);
	return solve();
}

Compilation message

horses.cpp: In function 'void updateBlock(int)':
horses.cpp:22:18: warning: conversion to 'll {aka long long int}' from 'double' may alter its value [-Wfloat-conversion]
  blc[p].mul = x[L];
               ~~~^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:57:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:6:11: note: shadowed declaration is here
 const int N = 5e5+10;
           ^
horses.cpp:65:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return solve();
         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:72:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return solve();
         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:79:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return solve();
         ~~~~~^~
horses.cpp: In function 'll solve()':
horses.cpp:39:11: warning: 'BlockNUM' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int idx, BlockNUM;
           ^~~~~~~~
horses.cpp:52:3: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(i == idx) ret = ret * (ll)y[j] % MOD;
   ^~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 2 ms 524 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 616 KB Output is correct
9 Correct 2 ms 616 KB Output is correct
10 Correct 2 ms 636 KB Output is correct
11 Correct 2 ms 636 KB Output is correct
12 Incorrect 2 ms 636 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Incorrect 3 ms 640 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1549 ms 17416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17416 KB Output is correct
2 Correct 2 ms 17416 KB Output is correct
3 Correct 2 ms 17416 KB Output is correct
4 Correct 2 ms 17416 KB Output is correct
5 Correct 3 ms 17416 KB Output is correct
6 Correct 2 ms 17416 KB Output is correct
7 Correct 2 ms 17416 KB Output is correct
8 Correct 2 ms 17416 KB Output is correct
9 Correct 2 ms 17416 KB Output is correct
10 Correct 2 ms 17416 KB Output is correct
11 Correct 2 ms 17416 KB Output is correct
12 Incorrect 2 ms 17416 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17416 KB Output is correct
2 Correct 3 ms 17416 KB Output is correct
3 Correct 2 ms 17416 KB Output is correct
4 Correct 2 ms 17416 KB Output is correct
5 Correct 2 ms 17416 KB Output is correct
6 Correct 2 ms 17416 KB Output is correct
7 Correct 2 ms 17416 KB Output is correct
8 Correct 2 ms 17416 KB Output is correct
9 Correct 2 ms 17416 KB Output is correct
10 Correct 2 ms 17416 KB Output is correct
11 Correct 2 ms 17416 KB Output is correct
12 Incorrect 2 ms 17416 KB Output isn't correct
13 Halted 0 ms 0 KB -