Submission #98922

#	Time	Username	Problem	Language	Result	Execution time	Memory
98922		psmao	Horses (IOI15_horses)	C++14	17 / 100	270 ms	50292 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)
	{
		int p = t[k].l;
		t[k].val = x[p];
		t[k].sum = log(1.0*x[p]);
		t[k].mx = log(1.0*x[p]*y[p]);
		t[k].res = x[p] * y[p] % P;
		return;
	}
	int mid = t[k].l + t[k].r >> 1;
	build(l, mid, k<<1);
	build(mid+1, r, k<<1|1);
	pu(k);
}
void upd(int p, int k=1)
{
	if(t[k].l == t[k].r)
	{
		t[k].val = x[p];
		t[k].sum = log(1.0*x[p]);
		t[k].mx = log(1.0*x[p]*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 (int)t[1].res;
}
int updateX(int pos, int val) {	
	x[pos+1] = val;
	upd(pos+1);
	return (int)t[1].res;
}

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

Compilation message (stderr)

horses.cpp: In function 'void build(int, int, int)':
horses.cpp:72: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:87:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = t[k].l + t[k].r >> 1;
            ~~~~~~~^~~~~~~~

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