Submission #309530

#	Time	Username	Problem	Language	Result	Execution time	Memory
309530		mihai145	Horses (IOI15_horses)	C++14	17 / 100	649 ms	53112 KiB

horses

#include "horses.h"
#include <set>
#include <vector>
#include <algorithm>

const int YMAX = 1e9;
const int MOD = 1e9 + 7;
const int NMAX = 5e5;

int n;
long long x[NMAX + 2], y[NMAX + 2];

struct Aintx {
    long long v[4 * NMAX];

    void Build(int node, int st, int dr)
        {
            if(st == dr)
                {
                    v[node] = x[st];
                    return ;
                }

            int mid = (st + dr) >> 1;

            Build(2 * node, st, mid);
            Build(2 * node + 1, mid + 1, dr);

            v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD;
        }

    void setx(int node, int st, int dr, int pos, long long val)
        {
            if(st == dr)
                {
                    v[node] = val;
                    return;
                }

            int mid = (st + dr) >> 1;
            if(pos <= mid)
                setx(2 * node, st, mid, pos, val);
            else
                setx(2 * node + 1, mid + 1, dr, pos, val);

            v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD;
        }

    long long queryx(int node, int st, int dr, int l, int r)
        {
            if(l <= st && dr <= r)
                return v[node];

            if(dr < l || st > r)
                return 1;

            int mid = (st + dr) >> 1;
            long long ans1 = queryx(2 * node, st, mid, l, r);
            long long ans2 = queryx(2 * node + 1, mid + 1, dr, l, r);

            return (1LL * ans1 * ans2) % MOD;
        }
};
Aintx aintx;

struct Ainty {
    long long v[4 * NMAX];

    void Build(int node, int st, int dr)
        {
            if(st == dr)
                {
                    v[node] = y[st];
                    return ;
                }

            int mid = (st + dr) >> 1;

            Build(2 * node, st, mid);
            Build(2 * node + 1, mid + 1, dr);

            v[node] = std::max(v[2 * node], v[2 * node + 1]);
        }

    void sety(int node, int st, int dr, int pos, long long val)
        {
            if(st == dr)
                {
                    v[node] = val;
                    return;
                }

            int mid = (st + dr) >> 1;
            if(pos <= mid)
                sety(2 * node, st, mid, pos, val);
            else
                sety(2 * node + 1, mid + 1, dr, pos, val);

            v[node] = std::max(v[2 * node], v[2 * node + 1]);
        }

    long long queryy(int node, int st, int dr, int l, int r)
        {
            if(l <= st && dr <= r)
                return v[node];

            if(dr < l || st > r)
                return 1LL;

            int mid = (st + dr) >> 1;
            int ans1 = queryy(2 * node, st, mid, l, r);
            int ans2 = queryy(2 * node + 1, mid + 1, dr, l, r);

            return std::max(ans1, ans2);
        }
};
Ainty ainty;

std::set <int> s;

int Query()
{
    long long prod = 1LL;
    std::vector <int> pos;
    for(auto it : s)
        {
            if(prod >= YMAX)
                break;

            pos.push_back(-it);
            prod *= x[-it];
        }

    int sz = (int)pos.size();
    long long px = 1LL, py = 0, mx = 0;

    for(int i = sz - 2; i >= 0; i--)
        {
            px *= x[pos[i]];

            if(i > 0)
                py = ainty.queryy(1, 1, n, pos[i], pos[i - 1] - 1);
            else
                py = ainty.queryy(1, 1, n, pos[i], n);

            mx = std::max(mx, px * py);
        }

    if(pos.back() == 0)
        {
            py = ainty.queryy(1, 1, n, 1, n);
            return std::max(mx, py) % MOD;
        }

    if(sz > 1)
        py = ainty.queryy(1, 1, n, pos[sz - 1], pos[sz - 2] - 1);
    else
        py = ainty.queryy(1, 1, n, pos[sz - 1], n);

    long long f = std::max(mx, py);
    return (1LL * f * aintx.queryx(1, 1, n, 1, pos[sz - 1])) % MOD;
}

int init(int N, int X[], int Y[]) {
    n = N;

    x[0] = 1LL;
    y[0] = 1LL;
    for(int i = 0; i < n; i++)
        x[i + 1] = 1LL * X[i], y[i + 1] = 1LL * Y[i];

    aintx.Build(1, 1, n);
    ainty.Build(1, 1, n);

    s.insert(0);
    for(int i = 1; i <= n; i++) {
        if(x[i] > 1) {
            s.insert(-i);
        }
    }

	return Query();
}

int updateX(int pos, int val) {
    pos++;
    if(x[pos] == val)
        return Query();

    aintx.setx(1, 1, n, pos, val);

    if(x[pos] > 1 && val == 1)
            s.erase(-pos);
    else if(x[pos] == 1 && val > 1)
            s.insert(-pos);

    x[pos] = 1LL * val;

	return Query();
}

int updateY(int pos, int val) {
    pos++;
    if(y[pos] == val)
        return Query();

    ainty.sety(1, 1, n, pos, val);
    y[pos] = 1LL * val;

	return Query();
}

Compilation message (stderr)

horses.cpp: In member function 'long long int Ainty::queryy(int, int, int, int, int)':
horses.cpp:111:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |             int ans1 = queryy(2 * node, st, mid, l, r);
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:112:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |             int ans2 = queryy(2 * node + 1, mid + 1, dr, l, r);
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int Query()':
horses.cpp:152:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  152 |             return std::max(mx, py) % MOD;
      |                    ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:161:62: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  161 |     return (1LL * f * aintx.queryx(1, 1, n, 1, pos[sz - 1])) % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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