Submission #735570

#	Time	Username	Problem	Language	Result	Execution time	Memory
735570		sandry24	Horses (IOI15_horses)	C++17	100 / 100	176 ms	58484 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second

const int mod = 1e9+7;
const int maxn = 500005;

struct node {
    double logsum;
    double bestlogsum;
    ll mult;
    ll bestmult;
};

int n;
node st[4*maxn];
ll x[maxn], y[maxn];

void combine(int v, int l, int r){
    st[v].logsum = st[l].logsum + st[r].logsum;
    st[v].mult = (st[l].mult * st[r].mult) % mod;
    if(st[l].bestlogsum > st[l].logsum + st[r].bestlogsum){
        st[v].bestlogsum = st[l].bestlogsum;
        st[v].bestmult = st[l].bestmult;
    } else {
        st[v].bestlogsum = st[l].logsum + st[r].bestlogsum;
        st[v].bestmult = (st[l].mult * st[r].bestmult) % mod;
    }
}

void build(int v, int tl, int tr){
    if(tl == tr){
        st[v].logsum = log10(x[tl]);
        st[v].mult = x[tl];
        st[v].bestlogsum = st[v].logsum + log10(y[tl]);
        st[v].bestmult = (st[v].mult * y[tl]) % mod;

    } else {
        int tm = (tl+tr)/2;
        build(v*2, tl, tm);
        build(v*2+1, tm+1, tr);
        combine(v, v*2, v*2+1);
    }
}

void update(int v, int tl, int tr, int pos, int val){
    if(tl == tr){
        st[v].logsum = log10(x[tl]);
        st[v].mult = x[tl];
        st[v].bestlogsum = st[v].logsum + log10(y[tl]);
        st[v].bestmult = (st[v].mult * y[tl]) % mod;
    } else {
        int tm = (tl+tr)/2;
        if(pos <= tm)
            update(v*2, tl, tm, pos, val);
        else
            update(v*2+1, tm+1, tr, pos, val);
        combine(v, v*2, v*2+1);
    }
}

int init(int N, int X[], int Y[]){
    n = N;
    for(int i = 0; i < N; i++){
        x[i] = X[i];
        y[i] = Y[i];
    }
    build(1, 0, n-1);
    return st[1].bestmult;
}

int updateX(int pos, int val){
    x[pos] = val;
    update(1, 0, n-1, pos, val);
    return st[1].bestmult;
}

int updateY(int pos, int val){
    y[pos] = val;
    update(1, 0, n-1, pos, val);
    return st[1].bestmult;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:79:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   79 |     return st[1].bestmult;
      |            ~~~~~~^~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:85:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   85 |     return st[1].bestmult;
      |            ~~~~~~^~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:91:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |     return st[1].bestmult;
      |            ~~~~~~^~~~~~~~

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