Submission #356616

#	Time	Username	Problem	Language	Result	Execution time	Memory
356616		blue	Horses (IOI15_horses)	C++17	57 / 100	1598 ms	171900 KiB

horses

#include "horses.h"
#include <iostream>
#include <string>
#include <set>
using namespace std;

long long mod = 1e9 + 7;

long long ll(int a)
{
    return (long long)(a);
}

struct segtree
{
    int l;
    int r;

    long long p_mod = 1;
    long long p_actual = 1;
    long long mx = 1;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;
        if(l == r) return;
        int m = (l+r)/2;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    long long rangeprod_mod(int L, int R)
    {
        if(L > R) return 1;
        if(r < L || R < l) return 1;
        if(L <= l && r <= R) return p_mod;
        return (left->rangeprod_mod(L, R) * right->rangeprod_mod(L, R)) % mod;
    }

    long long rangeprod_actual(int L, int R)
    {
        if(L > R) return 1;
        if(r < L || R < l) return 1;
        if(L <= l && r <= R) return p_actual;
        return left->rangeprod_actual(L, R) * right->rangeprod_actual(L, R);
    }

    long long rangemax(int L, int R)
    {
        if(r < L || R < l) return 0;
        if(L <= l && r <= R) return mx;
        return max(left->rangemax(L, R), right->rangemax(L, R));
    }

    void update(int I, long long V)
    {
        if(I < l || r < I) return;
        if(l == r)
        {
            p_mod = p_actual = mx = V;
        }
        else
        {
            left->update(I, V);
            right->update(I, V);
            p_mod = (left->p_mod * right->p_mod) % mod;
            p_actual = left->p_actual * right->p_actual;
            mx = max(left->mx, right->mx);
        }
    }
};

struct growth
{
    int i;
    long long x;
    long long y;
};

bool operator < (growth A, growth B)
{
    return A.i > B.i;
}

int N;
segtree X;
segtree Y;
set<growth> Xset;

int compute()
{
   // if(Xset.size() == 0) return Y.rangemax(0, N-1);

    long long maxprod = 1, maxprod_pos = 0;
    for(growth g: Xset)
    {
        maxprod *= g.x;
        if(maxprod > ll(1e9))
        {
            maxprod_pos = g.i + 1;
            break;
        }
    } //maxprod_pos is the last position with a suffix product <= 1e9

    long long res = 0, res_pos = -1;

    // for(int i = 0; i < N; i++) cout << X.rangeprod_mod(i, i) << ' ';
    // cout << '\n';
    // for(int i = 0; i < N; i++) cout << X.rangeprod_actual(i, i) << ' ';
    // cout << '\n';
    // for(int i = 0; i < N; i++) cout << Y.rangemax(i, i) << ' ';
    // cout << '\n';

    for(growth g: Xset)
    {
        if(g.i < maxprod_pos - 1) break;
        if(X.rangeprod_actual(maxprod_pos, g.i) * Y.rangemax(g.i, N-1) >= res)
        {
            res = X.rangeprod_actual(maxprod_pos, g.i) * Y.rangemax(g.i, N-1);
            res_pos = g.i;
        }
        // if(g.i > 0 && X.rangeprod_actual(maxprod_pos, g.i-1) * Y.rangemax(g.i-1, N-1) > res)
        // {
        //     res = X.rangeprod_actual(maxprod_pos, g.i-1) * Y.rangemax(g.i-1, N-1);
        //     res_pos = g.i-1;
        // }
    }

    return int( (X.rangeprod_mod(0, res_pos) * Y.rangemax(res_pos, N-1)) % mod );
}

int init(int n, int x[], int y[])
{
    N = n;
    X = segtree(0, N-1);
    Y = segtree(0, N-1);

    long long nxt = N-1;

    for(int i = 0; i < N; i++)
    {
        Y.update(i, ll(y[i]));

        X.update(i, x[i]);
        if(x[i] != 1)
        {
            Xset.insert(growth{i, ll(x[i]), Y.rangemax(i, nxt)});
            nxt = i-1;
        }
    }

    Xset.insert(growth{-1, 1, Y.rangemax(0, nxt)});

    return compute();
}

int updateX(int pos, int val)
{
    int curr_val = X.rangemax(pos, pos);
    if(curr_val != 1) Xset.erase(growth{pos, curr_val});

    X.update(pos, val);
    if(val != 1) Xset.insert(growth{pos, val});
    return compute();
}

int updateY(int pos, int val)
{
    Y.update(pos, val);
    set<growth>::iterator it = Xset.upper_bound(growth{pos, -1, -1});

    growth temp;

    // if(it == Xset.end())
    // {
    //     it--;
    //     temp = *it;
    //     Xset.erase(temp);
    //     temp.y = Y.rangemax(temp.i, N-1);
    //     Xset.insert(temp);
    // }
    // else
    // {
    //     int j = it->i - 1;
    //     it--;
    //     temp = *it;
    //     Xset.erase(temp);
    //     temp.y = Y.rangemax(temp.i, j);
    //     Xset.insert(temp);
    // }

    return compute();
}

Compilation message (stderr)

horses.cpp: In function 'int compute()':
horses.cpp:126:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  126 |         if(X.rangeprod_actual(maxprod_pos, g.i) * Y.rangemax(g.i, N-1) >= res)
      |                               ^~~~~~~~~~~
horses.cpp:128:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  128 |             res = X.rangeprod_actual(maxprod_pos, g.i) * Y.rangemax(g.i, N-1);
      |                                      ^~~~~~~~~~~
horses.cpp:138:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  138 |     return int( (X.rangeprod_mod(0, res_pos) * Y.rangemax(res_pos, N-1)) % mod );
      |                                     ^~~~~~~
horses.cpp:138:59: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  138 |     return int( (X.rangeprod_mod(0, res_pos) * Y.rangemax(res_pos, N-1)) % mod );
      |                                                           ^~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:156:59: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  156 |             Xset.insert(growth{i, ll(x[i]), Y.rangemax(i, nxt)});
      |                                                           ^~~
horses.cpp:161:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  161 |     Xset.insert(growth{-1, 1, Y.rangemax(0, nxt)});
      |                                             ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:168:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  168 |     int curr_val = X.rangemax(pos, pos);
      |                    ~~~~~~~~~~^~~~~~~~~~
horses.cpp:169:54: warning: missing initializer for member 'growth::y' [-Wmissing-field-initializers]
  169 |     if(curr_val != 1) Xset.erase(growth{pos, curr_val});
      |                                                      ^
horses.cpp:172:45: warning: missing initializer for member 'growth::y' [-Wmissing-field-initializers]
  172 |     if(val != 1) Xset.insert(growth{pos, val});
      |                                             ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:179:27: warning: variable 'it' set but not used [-Wunused-but-set-variable]
  179 |     set<growth>::iterator it = Xset.upper_bound(growth{pos, -1, -1});
      |                           ^~
horses.cpp:181:12: warning: unused variable 'temp' [-Wunused-variable]
  181 |     growth temp;
      |            ^~~~

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