Submission #288368

#	Time	Username	Problem	Language	Result	Execution time	Memory
288368		Kastanda	Horses (IOI15_horses)	C++11	100 / 100	183 ms	50296 KiB

horses

// M
#include<bits/stdc++.h>
#include "horses.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int N = 500005, Mod = 1e9 + 7;
const ll INF = 1e9 + 100;
struct Data {int rs, mlx; ll pref, suff, opty, multx;};
int n, X[N], Y[N];
Data D[N * 4];
inline void Recalc(int id)
{
        D[id].mlx = D[lc].mlx * (ll)D[rc].mlx % Mod;
        D[id].multx = min(D[lc].multx * (ll)D[rc].multx, INF);
        if (D[lc].opty > D[lc].suff * (ll)D[rc].pref)
        {
                D[id].opty = D[lc].opty;
                D[id].rs = D[lc].rs;
                D[id].pref = D[lc].pref;
                D[id].suff = min((ll)D[lc].suff * D[rc].multx, INF);
        }
        else
        {
                D[id].opty = D[rc].opty;
                D[id].rs = D[lc].mlx * (ll)D[rc].rs % Mod;
                D[id].pref = min(D[lc].multx * (ll)D[rc].pref, INF);
                D[id].suff = D[rc].suff;
        }
}
void Build(int id = 1, int l = 0, int r = n)
{
        if (r - l < 2)
        {
                D[id].rs = (ll)X[l] * Y[l] % Mod;
                D[id].mlx = X[l] % Mod;
                D[id].multx = min((ll)X[l], INF);
                D[id].pref = min((ll)X[l] * Y[l], INF);
                D[id].suff = 1LL;
                D[id].opty = Y[l];
                return ;
        }
        Build(lc, l, md);
        Build(rc, md, r);
        Recalc(id);
}
void UpdXVal(int i, int id = 1, int l = 0, int r = n)
{
        if (r - l < 2)
        {
                D[id].rs = (ll)X[l] * Y[l] % Mod;
                D[id].mlx = X[l] % Mod;
                D[id].multx = min((ll)X[l], INF);
                D[id].pref = min((ll)X[l] * Y[l], INF);
                D[id].suff = 1LL;
                D[id].opty = Y[l];
                return ;
        }
        if (i < md)
                UpdXVal(i, lc, l, md);
        else
                UpdXVal(i, rc, md, r);
        Recalc(id);
}

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();
        return D[1].rs;
}

int updateX(int pos, int val)
{
        X[pos] = val;
        UpdXVal(pos);
        return D[1].rs;
}

int updateY(int pos, int val)
{
        Y[pos] = val;
        UpdXVal(pos);
        return D[1].rs;
}

Compilation message (stderr)

horses.cpp: In function 'void Recalc(int)':
horses.cpp:16:47: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   16 |         D[id].mlx = D[lc].mlx * (ll)D[rc].mlx % Mod;
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:28:53: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   28 |                 D[id].rs = D[lc].mlx * (ll)D[rc].rs % Mod;
      |                            ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void Build(int, int, int)':
horses.cpp:37:44: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   37 |                 D[id].rs = (ll)X[l] * Y[l] % Mod;
      |                            ~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void UpdXVal(int, int, int, int)':
horses.cpp:53:44: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   53 |                 D[id].rs = (ll)X[l] * Y[l] % Mod;
      |                            ~~~~~~~~~~~~~~~~^~~~~

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