Submission #119721

#	Time	Username	Problem	Language	Result	Execution time	Memory
119721		CaroLinda	Horses (IOI15_horses)	C++14	17 / 100	17 ms	9856 KiB

horses

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

#define lp(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define pii pair<int,int>
#define ff first
#define ss second

//ARRUMAR O MAXN

const int maxn=5e3+10 ;
const int MOD=1e9+7 ;

using namespace std ;

struct node
{
  double a , la ;
  ll b , lb1 , lb2 ;
  node()
  {
    a = la = 0 ;
    b = lb1 = lb2 = 1 ;
  }
} ;

node tree[4*maxn] ;

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

void refresh(int pos, int l, int r)
{

  double k1 = tree[pos].la ;
  ll k2 = tree[pos].lb1 ;
  ll k3 = tree[pos].lb2 ;

  tree[pos].la = 0 ;
  tree[pos].lb1 = 1 ;
  tree[pos].lb2 = 1 ;

  tree[pos].b = (tree[pos].b/k3) ;
  tree[pos].b = (tree[pos].b*k2) % MOD ;
  tree[pos].a += k1 ;

  if(l==r) return ;

  lp(i,0,2)
  {
    tree[pos*2+i].la += k1 ;
    tree[pos*2+i].lb1 = (tree[pos*2+i].lb1*k2) % MOD ;
    tree[pos*2+i].lb2 = (tree[pos*2+i].lb2*k3) % MOD ;
  }
 
}

void merge(int pos)
{
  tree[pos].a = max(tree[pos*2].a, tree[pos*2+1].a) ;
  tree[pos].b = (tree[pos*2].a > tree[pos*2+1].a) ? tree[pos*2].b : tree[pos*2+1].b ;
}

void pointUpd(int pos, int l, int r ,int x, double v, ll b1 , ll b2) 
{
  refresh(pos,l,r) ;
  if(l>x or r < x) return ;
  if(l==r)
  { 
    tree[pos].a += v ; 
    tree[pos].b = tree[pos].b/b2 ;
    tree[pos].b = (tree[pos].b*b1)%MOD ;
    return ; 
  }

  pointUpd(pos*2,l,m(l,r),x,v,b1,b2) ;
  pointUpd(pos*2+1,m(l,r)+1,r,x,v,b1,b2) ;

  merge(pos) ;

}

void intervalUpd(int pos, int l, int r , int beg, int en, double v, ll b1 ,ll b2)
{
  refresh(pos, l, r) ;
  if(l>en or r < beg) return ;
  if(l>=beg && r<=en)
  {
    tree[pos].la += v ;
    tree[pos].lb1 = (tree[pos].lb1*b1) % MOD ;
    tree[pos].lb2 = (tree[pos].lb2*b2) % MOD ;
    refresh(pos, l, r) ;
    return ;
  }
  intervalUpd(pos*2, l,m(l,r),beg,en,v,b1,b2) ;
  intervalUpd(pos*2+1,m(l,r)+1,r,beg,en,v,b1,b2) ;
  merge(pos) ;
}

void print(int pos, int l, int r)
{
  refresh(pos,l,r) ;
  printf("%d e %d: %lld\n", l,r,tree[pos].b) ;
  if(l==r) return ;
  print(pos*2,l,m(l,r)) ;
  print(pos*2+1,m(l,r)+1,r) ;
}

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

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

ll ans()
{
  refresh(1,0,n-1) ;
  return tree[1].b ;
}

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

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

int init(int N, int X[], int Y[])
{
  n = N ;
  lp(i,0,n) x[i] = X[i] ;
  lp(i,0,n) y[i]=Y[i] ;

  ll acProduct=1 ;
  double logProduct = log2(1) ;

  lp(i,0,n)
  {
    acProduct = (acProduct*x[i]) % MOD ;
    logProduct += log2(x[i]) ;

    pointUpd(1,0,n-1,i,log2(y[i]) + logProduct , (acProduct*y[i])%MOD,1 ) ;

  }

  return ans();

}

Compilation message (stderr)

horses.cpp: In function 'int updateY(int, int)':
horses.cpp:123:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return ans() ;
          ~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:130:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return ans() ;
          ~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:151:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return ans();
          ~~~^~

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