Submission #65647

#	Time	Username	Problem	Language	Result	Execution time	Memory
65647		mirbek01	Horses (IOI15_horses)	C++17	100 / 100	267 ms	276984 KiB

horses

#include "horses.h"

# include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int N = 5e5 + 2;

int n, X[N], Y[N];

double x[N], y[N];

struct node{
      double sum, pref;
      long long res, pr;
};

node t[N * 4];

inline node combine (node a, node b)
{
      node c;
      c.sum = a.sum + b.sum;
      c.res = a.res * b.res % mod;
      if (a.pref > a.sum + b.pref)
      {
            c.pref = a.pref;
            c.pr = a.pr;
      }
      else
      {
            c.pref = a.sum + b.pref;
            c.pr = a.res * b.pr % mod;
      }
      return c;
}

void build(int v = 1, int tl = 0, int tr = n - 1){
      if (tl == tr)
      {
            t[v].sum = x[tl];
            t[v].pref = x[tl] + y[tl];
            t[v].res = X[tl];
            t[v].pr = X[tl] * 1ll * Y[tl] % mod;
      }
      else
      {
            int tm = (tl + tr) >> 1;
            build( v + v, tl, tm );
            build( v + v + 1, tm + 1, tr );

            t[v] = combine( t[v + v], t[v + v + 1] );
      }
}

int init(int NN, int a[], int b[]) {
      n = NN;
      for(int i = 0; i < n; i ++)
            x[i] = log10(a[i]), y[i] = log10(b[i]), X[i] = a[i], Y[i] = b[i];
      build();

      return t[1].pr;
}

void update (int pos, int val, int v = 1, int tl = 0, int tr = n - 1)
{
      if (tl == tr)
      {
            t[v].sum = x[tl];
            t[v].pref = x[tl] + y[tl];
            t[v].res = X[tl];
            t[v].pr = X[tl] * 1ll * Y[tl] % mod;
      }
      else
      {
            int tm = (tl + tr) >> 1;
            if (pos <= tm)
                  update( pos, val, v + v, tl, tm );
            else
                  update( pos, val, v + v + 1, tm + 1, tr );

            t[v] = combine( t[v + v], t[v + v + 1] );
      }
}

int updateX(int pos, int val) {
      X[pos] = val;
      x[pos] = log10(val);
      update( pos, val );

      return t[1].pr;
}

int updateY(int pos, int val) {
      Y[pos] = val;
      y[pos] = log10(val);
      update( pos, val );

      return t[1].pr;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:63:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
       return t[1].pr;
              ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:92:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
       return t[1].pr;
              ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:100:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
       return t[1].pr;
              ~~~~~^~

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