Submission #121909

#	Time	Username	Problem	Language	Result	Execution time	Memory
121909		CaroLinda	Horses (IOI15_horses)	C++14	100 / 100	501 ms	54520 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"

#define ll long long
#define lp(i,a,b) for(int i=a;i<b;i++)

const int MAXN=5e5+5 ;
const int MOD=1e9+7 ;

using namespace std ;

// -------------x-------------

int n, x[MAXN],y[MAXN] ;

struct node
{
	double v , l ;
	int best ;
	ll real ;
} ;

node tree[MAXN*4] ;

// -------------x-------------

int m(int l, int r) {return (l+r)/2 ;}

void refresh(int pos, int l, int r)
{
	double k = tree[pos].l ;
	tree[pos].l = 0 ;
	tree[pos].v += k ;
	if(l==r) return ;
	lp(i,0,2) tree[pos*2+i].l += k ;
}

void merge(int pos)
{
	tree[pos] = (tree[pos*2].v > tree[pos*2+1].v) ? tree[pos*2] : tree[pos*2+1] ;
	tree[pos].real = tree[pos*2].real * tree[pos*2+1].real % MOD ;
}

void build(int pos, int l, int r)
{
	if(l==r)
	{
		tree[pos].v = log2(y[l]) ;
		tree[pos].real = x[l] ;
		tree[pos].best = l ;
		tree[pos].l = 0 ;
		return ;
	}
	build(pos*2,l,m(l,r)) ;
	build(pos*2+1, m(l,r)+1,r) ;
	merge(pos) ;
}

void pointUpd(int pos, int l, int r, int x, int val)
{
	refresh(pos,l,r) ;
	if(l>x || r<x) return ;
	if(l==r)
	{
		tree[pos].real = val ;
		return ;
	}
	pointUpd(pos*2,l,m(l,r),x,val) ;
	pointUpd(pos*2+1,m(l,r)+1,r,x,val) ;
	merge(pos) ;
}

void intervalUpd(int pos, int l, int r, int beg, int en, double val )
{
	refresh(pos,l,r) ;
	if(l>en || r<beg) return ;
	if(l>=beg && r<=en)
	{
		tree[pos].l += val ;
		refresh(pos,l,r) ;
		return ;
	}
	intervalUpd(pos*2,l,m(l,r),beg,en,val) ;
	intervalUpd(pos*2+1,m(l,r)+1,r,beg,en,val) ;
	merge(pos) ;
}

ll query(int pos, int l, int r, int beg, int en)
{
	if(l>en || r<beg) return 1 ;
	if(l>=beg && r<=en) return tree[pos].real ;
	ll rl = query(pos*2,l,m(l,r),beg,en) ;
	ll rr=query(pos*2+1,m(l,r)+1,r,beg,en) ;
	return rl*rr%MOD ;
}

int ans()
{
	refresh(1,0,n-1) ;
	int myBest = tree[1].best ;
	return query(1,0,n-1,0,myBest)*y[myBest]%MOD ;
}

int init(int N, int X[] ,  int Y[])
{
	n=N;
	lp(i,0,n) x[i]=X[i],y[i]=Y[i] ;
	
	build(1,0,n-1) ;
	lp(i,0,n) intervalUpd(1,0,n-1,i,n-1,log2(x[i])) ;
	return ans() ;
	
}

int updateY(int pos, int val)
{
	intervalUpd(1,0,n-1,pos,pos,-log2(y[pos]) + log2(val)) ;
	y[pos]=val ;
	return ans() ;
}

int updateX(int pos, int val)
{
	pointUpd(1,0,n-1,pos,val) ;
	intervalUpd(1,0,n-1,pos,n-1,-log2(x[pos])+log2(val) ) ;
	x[pos]=val ;
	return ans() ;
}

Compilation message (stderr)

horses.cpp: In function 'void pointUpd(int, int, int, int, int)':
horses.cpp:59:52: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 void pointUpd(int pos, int l, int r, int x, int val)
                                                    ^
horses.cpp:14:8: note: shadowed declaration is here
 int n, x[MAXN],y[MAXN] ;
        ^
horses.cpp: In function 'int ans()':
horses.cpp:101:42: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return query(1,0,n-1,0,myBest)*y[myBest]%MOD ;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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