Submission #725998

#	Time	Username	Problem	Language	Result	Execution time	Memory
725998		TheSahib	Horses (IOI15_horses)	C++17	34 / 100	1565 ms	24324 KiB

horses

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

#define ll long long
#define pii pair<int, ll>

using namespace std;

const int MOD = 1e9 + 7;
const ll oo = 1e9 + 9;
const int MAX = 5e5 + 5;

struct DATA{
    int index, leftMultipliyer, rightMultiplier;
};

int n;
int price[MAX], cnt[MAX];
DATA tree[MAX * 4];


DATA merge(DATA a, DATA b){
    ll m = min(oo, 1ll * a.rightMultiplier * b.leftMultipliyer);
    if(price[a.index] / m >= price[b.index]){
        return {a.index, a.leftMultipliyer, min(oo, m * b.rightMultiplier)};
    }
    else{
        return {b.index, min(oo, m * a.leftMultipliyer), b.rightMultiplier};
    }
}

void build(int node, int l, int r){
    if(l == r){
        tree[node] = {l, cnt[l], 1};
        return;
    }

    int mid = (l + r) / 2;
    build(node << 1 | 1, l, mid);
    build((node + 1) << 1, mid + 1, r);

    tree[node] = merge(tree[(node << 1) | 1], tree[(node + 1) << 1]);
}

int calcAns(){
    DATA ans = tree[0];
    ll a = 1;
    for (int i = 0; i <= ans.index; i++)
    {
        a *= cnt[i];
        a %= MOD;
    }
    a = (a * price[ans.index]) % MOD;
    return a;
}


int init(int N, int X[], int Y[]) {
    n = N;
    for (int i = 0; i < n; i++)
    {
        cnt[i] = X[i];
        price[i] = Y[i];
    }
    build(0, 0, n - 1);
    return calcAns();
}

int updateX(int pos, int val) {	
	cnt[pos] = val;
    build(0, 0, n - 1);
    return calcAns();
}

int updateY(int pos, int val) {
	price[pos] = val;
    build(0, 0, n - 1);
    return calcAns();
}

Compilation message (stderr)

horses.cpp: In function 'DATA merge(DATA, DATA)':
horses.cpp:25:48: warning: narrowing conversion of '(long long int)std::min<long long int>(oo, (m * ((long long int)b.DATA::rightMultiplier)))' from 'long long int' to 'int' [-Wnarrowing]
   25 |         return {a.index, a.leftMultipliyer, min(oo, m * b.rightMultiplier)};
      |                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:25:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
horses.cpp:28:29: warning: narrowing conversion of '(long long int)std::min<long long int>(oo, (m * ((long long int)a.DATA::leftMultipliyer)))' from 'long long int' to 'int' [-Wnarrowing]
   28 |         return {b.index, min(oo, m * a.leftMultipliyer), b.rightMultiplier};
      |                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:28:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
horses.cpp: In function 'int calcAns()':
horses.cpp:54:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   54 |     return a;
      |            ^

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