Submission #795459

#	Time	Username	Problem	Language	Result	Execution time	Memory
795459		Ronin13	Horses (IOI15_horses)	C++17	34 / 100	65 ms	66628 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back

const int nmax = 200001;
const ll mod = 1e9 + 7;
struct node{
	double sum, mx = 0;
	ll ans;
	ll x;
	node(){
		sum = mx = 0;
		ans = 1;
		x = 1;
	}

}t[4 * nmax];

ll x[nmax], y[nmax];

node merg(node a, node b){
	node c;
	c.sum = a.sum + b.sum;
	c.x = a.x * b.x % mod;
	if(a.mx > a.sum + b.mx){
		c.mx = a.mx;
		c.ans = a.ans;
	}
	else{
		c.mx = a.sum + b.mx;
		c.ans = b.ans * a.x % mod;
	}
	return c;
}

void build(int v, int l, int r){
	if(l == r){
		t[v].sum = log2(x[l]);
		t[v].mx = log2(x[l]) + log2(y[l]);
		t[v].ans = x[l] * y[l] % mod;
		t[v].x = x[l];
		return;
	}
	int m = (l + r) / 2;
	build(2 * v, l, m);
	build(2 * v+ 1, m + 1, r);
	t[v] = merg(t[2 * v], t[2 * v + 1]);
}

void update(int v, int l, int r, int pos, int val, int ind){
	if(l > pos || r < pos)
		return;
	if(l == r){
		if(ind == 0) x[l] = val;
		else y[l] = val;
		t[v].sum = log2(x[l]);
		t[v].mx = log2(x[l]) + log2(y[l]);
		t[v].ans = x[l] * y[l] % mod;
		t[v].x = x[l];
		return;
	}
	int m = (l + r) / 2;
	update(2 * v, l, m, pos, val, ind);
	update(2 * v+ 1, m + 1, r, pos, val, ind);
	t[v] = merg(t[2 * v], t[2 * v + 1]);
}
int n;
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];
	}
	build(1, 0, n - 1);
	return t[1].ans;
}

int updateX(int pos, int val) {	
	update(1, 0, n - 1, pos, val, 0);
	return t[1].ans;
}

int updateY(int pos, int val) {
	update(1, 0, n - 1, pos, val, 1);
	return t[1].ans;
}

Compilation message (stderr)

horses.cpp: In function 'void build(int, int, int)':
horses.cpp:45:22: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   45 |   t[v].sum = log2(x[l]);
      |                   ~~~^
horses.cpp:46:21: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   46 |   t[v].mx = log2(x[l]) + log2(y[l]);
      |                  ~~~^
horses.cpp:46:34: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   46 |   t[v].mx = log2(x[l]) + log2(y[l]);
      |                               ~~~^
horses.cpp: In function 'void update(int, int, int, int, int, int)':
horses.cpp:63:22: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   63 |   t[v].sum = log2(x[l]);
      |                   ~~~^
horses.cpp:64:21: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   64 |   t[v].mx = log2(x[l]) + log2(y[l]);
      |                  ~~~^
horses.cpp:64:34: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   64 |   t[v].mx = log2(x[l]) + log2(y[l]);
      |                               ~~~^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:81:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |  return t[1].ans;
      |         ~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:86:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |  return t[1].ans;
      |         ~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:91:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |  return t[1].ans;
      |         ~~~~~^~~

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