Submission #98914

#	Time	Username	Problem	Language	Result	Execution time	Memory
98914		psmao	Horses (IOI15_horses)	C++14	17 / 100	583 ms	62968 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}

const int maxn = 500050;
const int P = 1e9+7;

struct node
{
	int l, r;
	ll val, res;
	double sum, mx;
}t[maxn<<2];
int x[maxn], y[maxn];

void pu(int k)
{
	if(t[k<<1].mx < t[k<<1].sum + t[k<<1|1].mx)
	{
		t[k].mx = t[k<<1].sum + t[k<<1|1].mx;
		t[k].res = t[k<<1].val * t[k<<1|1].res % P;
	}
	else
	{
		t[k].mx = t[k<<1].mx;
		t[k].res = t[k<<1].res;
	}
	t[k].sum = t[k<<1].sum + t[k<<1|1].sum;
	t[k].val = t[k<<1].val * t[k<<1|1].val % P;
}
void build(int l, int r, int k = 1)
{
	t[k].l = l; t[k].r = r;
	if(l == r) return;
	int mid = t[k].l + t[k].r >> 1;
	build(l, mid, k<<1);
	build(mid+1, r, k<<1|1);
}
void upd(int p, int k=1)
{
	// D("%d %d %lld %d\n",t[k].l,t[k].r,t[k].res,k);
	if(t[k].l == t[k].r)
	{
		t[k].val = x[p];
		t[k].sum = log(x[p]);
		t[k].mx = log(x[p]) + log(y[p]);
		t[k].res = x[p] * y[p] % P;
		return;
	}
	int mid = t[k].l + t[k].r >> 1;
	if(p <= mid) upd(p, k<<1);
	else upd(p, k<<1|1);
	pu(k);
}
int init(int N, int X[], int Y[]) {
	fo(i,0,N-1) x[i+1] = X[i], y[i+1] = Y[i];
	build(1,N);
	fo(i,1,N) upd(i);
	return t[1].res;
}
int updateX(int pos, int val) {	
	x[pos+1] = val;
	upd(pos+1);
	return t[1].res;
}

int updateY(int pos, int val) {
	y[pos+1] = val;
	upd(pos+1);
	return t[1].res;
}

Compilation message (stderr)

horses.cpp: In function 'void build(int, int, int)':
horses.cpp:64:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = t[k].l + t[k].r >> 1;
            ~~~~~~~^~~~~~~~
horses.cpp: In function 'void upd(int, int)':
horses.cpp:79:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = t[k].l + t[k].r >> 1;
            ~~~~~~~^~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:88:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return t[1].res;
         ~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:93:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return t[1].res;
         ~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:99:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return t[1].res;
         ~~~~~^~~

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