Submission #119665

#	Time	Username	Problem	Language	Result	Execution time	Memory
119665		CaroLinda	Horses (IOI15_horses)	C++14	0 / 100	415 ms	34640 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

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

using namespace std ;

struct seg
{

  double tree[maxn*4] ;
  double lazy[maxn*4] ;
  ll realVal[maxn*4] ;

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

  void build(int pos, int l, int r)
  {
    realVal[pos]=1 ;
    if(l==r) return ;
    build(pos*2, l, m(l,r) ) ;
    build(pos*2+1, m(l,r)+1,r) ;
  }

  void updRealVal(int pos, double k)
  {
    ll kk = 1LL*pow(2,k) ;
    realVal[pos] = (realVal[pos]*kk) % MOD ;
  }

  void merge(int pos)
  {
    tree[pos] = max(tree[pos*2], tree[pos*2+1]) ;

    realVal[pos] = (tree[pos*2] > tree[pos*2+1]) ? realVal[pos*2] : realVal[pos*2+1] ;
  }

  void refresh(int pos, int l, int r)
  {
    double k=lazy[pos] ;
    lazy[pos]=0 ;

    tree[pos] += k ;

    updRealVal(pos,k) ;

    if(l==r) return ;

    lazy[pos*2]+=k;
    lazy[pos*2+1]+=k;

  }

  void pointUpd(int pos,int l,int r,int x, double val)
  {
    refresh(pos, l, r) ;
    if(l>x || r<x) return ;
    if(l==r)
    {
      tree[pos] += val ;
      updRealVal(pos,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)
    {
      lazy[pos] += 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) ;

  }

} ;

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

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

int updateX(int pos, int val)
{
  double newVal = 1.0*val/x[pos] ;
  x[pos] = val ;

  newVal = log2(newVal) ;

  mySeg.intervalUpd(1,0,n-1,pos,n-1,newVal) ;
  mySeg.refresh(1,0,n-1) ;

  return mySeg.realVal[1] ;

}

int updateY(int pos, int val)
{
  double newVal = 1.0*val/y[pos] ;
  y[pos]=val ;

  newVal = log2(newVal) ;

  mySeg.pointUpd(1,0,n-1,pos,newVal) ;
  mySeg.refresh(1,0,n-1) ;

  return mySeg.realVal[1] ;

}

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] ;

  mySeg.build(1,0,n-1) ;
  double acProduct = log2(1) ;

  lp(i,0,n)
  {
    acProduct += log2(x[i]) ;
    mySeg.pointUpd(1,0,n-1,i,acProduct+log2(y[i])) ;
  }

  return mySeg.realVal[1] ;

}

Compilation message (stderr)

horses.cpp: In member function 'void seg::updRealVal(int, double)':
horses.cpp:31:16: warning: conversion to 'long long int' from '__gnu_cxx::__promote_2<int, double, double, double>::__type {aka double}' may alter its value [-Wfloat-conversion]
     ll kk = 1LL*pow(2,k) ;
             ~~~^~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:112:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return mySeg.realVal[1] ;
          ~~~~~~~~~~~~~~~^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:126:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return mySeg.realVal[1] ;
          ~~~~~~~~~~~~~~~^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:145:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return mySeg.realVal[1] ;
          ~~~~~~~~~~~~~~~^

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