Submission #241000

#	Time	Username	Problem	Language	Result	Execution time	Memory
241000		ant101	Horses (IOI15_horses)	C++14	100 / 100	846 ms	45432 KiB

horses

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

#define left (index << 1)
#define right ((index << 1) + 1)
#define mid ((l + r) / 2)

const int MAXA = (int)1e9 + 1;
const int mod = (int)1e9 + 7;

int n;
vector<int> x, y;
vector<int> p, p2;
void buildP(int index, int l, int r)
{
    if (l == r)
    {
        p[index] = p2[index] = x[l];
        return;
    }
    buildP(left, l, mid);
    buildP(right, mid + 1, r);
    p[index] = (1LL * p[left] * p[right]) % mod;
    p2[index] = min((ll)MAXA, 1LL * p2[left] * p2[right]);
}
void updateP(int index, int l, int r, int ind)
{
    if (!(ind >= l && ind <= r))
        return;
    if (l == r)
    {
        p[index] = p2[index] = x[ind];
        return;
    }
    updateP(left, l, mid, ind);
    updateP(right, mid + 1, r, ind);
    p[index] = (1LL * p[left] * p[right]) % mod;
    p2[index] = min((ll)MAXA, 1LL * p2[left] * p2[right]);
}
int queryP(int index, int l, int r, int ql, int qr, bool foo)
{
    if (l > qr || r < ql)
        return 1;
    if (l >= ql && r <= qr)
        return foo ? p2[index] : p[index];
    if (foo)
        return min((ll)MAXA, (1LL * queryP(left, l, mid, ql, qr, true) * queryP(right, mid + 1, r, ql, qr, true)));
    return (1LL * queryP(left, l, mid, ql, qr, false) * queryP(right, mid + 1, r, ql, qr, false)) % mod;
}

vector<int> st;
void build(int index, int l, int r)
{
    if (l == r)
    {
        st[index] = l;
        return;
    }
    build(left, l, mid);
    build(right, mid + 1, r);
    int lll = st[left],
        rrr = st[right];
    if (queryP(1, 0, n - 1, lll + 1, rrr, true) >= ceil(y[lll] / (double)y[rrr]))
        st[index] = rrr;
    else st[index] = lll;
}
void update(int index, int l, int r, int ind)
{
    if (!(ind >= l && ind <= r))
        return;
    if (l == r)
        return;
    update(left, l, mid, ind);
    update(right, mid + 1, r, ind);
    int lll = st[left],
        rrr = st[right];
    if (queryP(1, 0, n - 1, lll + 1, rrr, true) >= (int)ceil(y[lll] / (double)y[rrr]))
        st[index] = rrr;
    else st[index] = lll;
}

int solve()
{
    int ind = st[1];
    //cout << ind << endl;
    return (1LL * queryP(1, 0, n - 1, 0, ind, false) * y[ind]) % mod;
}

int init(int N, int X[], int Y[])
{
    x = y = vector<int>(N);
    for (int i = 0; i < N; i++)
        x[i] = X[i], y[i] = Y[i];
    p = p2 = st = vector<int>(N * 4);
    n = N;
    buildP(1, 0, n - 1);
    build(1, 0, n - 1);
    return solve();
}

int updateX(int pos, int val)
{
    x[pos] = val;
    updateP(1, 0, n - 1, pos);
    update(1, 0, n - 1, pos);
    //buildP(1, 0, n - 1);
    //build(1, 0, n - 1);
    return solve();
}

int updateY(int pos, int val)
{
    y[pos] = val;
    update(1, 0, n - 1, pos);
    //buildP(1, 0, n - 1);
    //build(1, 0, n - 1);
    return solve();
}

Compilation message (stderr)

horses.cpp: In function 'void buildP(int, int, int)':
horses.cpp:30:43: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'long long int' may alter its value [-Wconversion]
     p[index] = (1LL * p[left] * p[right]) % mod;
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:31:20: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'long long int' may alter its value [-Wconversion]
     p2[index] = min((ll)MAXA, 1LL * p2[left] * p2[right]);
                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'void updateP(int, int, int, int)':
horses.cpp:44:43: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'long long int' may alter its value [-Wconversion]
     p[index] = (1LL * p[left] * p[right]) % mod;
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:45:20: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'long long int' may alter its value [-Wconversion]
     p2[index] = min((ll)MAXA, 1LL * p2[left] * p2[right]);
                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int queryP(int, int, int, int, int, bool)':
horses.cpp:54:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         return min((ll)MAXA, (1LL * queryP(left, l, mid, ql, qr, true) * queryP(right, mid + 1, r, ql, qr, true)));
                ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:55:99: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return (1LL * queryP(left, l, mid, ql, qr, false) * queryP(right, mid + 1, r, ql, qr, false)) % mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int solve()':
horses.cpp:93:64: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return (1LL * queryP(1, 0, n - 1, 0, ind, false) * y[ind]) % mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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