Submission #309513

#	Time	Username	Problem	Language	Result	Execution time	Memory
309513		mihai145	Horses (IOI15_horses)	C++14	17 / 100	566 ms	40892 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, x[NMAX + 2], y[NMAX + 2];

struct Aintx {
    int 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, int 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;
        }

    int queryx(int node, int st, int dr, int l, int r)
        {
            if(st > dr)
                return 0;

            if(l <= st && dr <= r)
                return v[node];

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

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

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

struct Ainty {
    int 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, int 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]);
        }

    int queryy(int node, int st, int dr, int l, int r)
        {
            if(st > dr)
                return 0;

            if(l <= st && dr <= r)
                return v[node];

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

            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)
        {
            pos.push_back(-it);
            prod *= x[-it];

            if(prod >= YMAX)
                break;
        }

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

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

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

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

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

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

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

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];

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

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

	return Query();
}

int updateX(int pos, int val) {

    if(x[pos] == val)
        return Query();

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

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

    x[pos] = val;

	return Query();
}

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

    ainty.sety(1, 0, n - 1, pos, val);
    y[pos] = val;

	return Query();
}

Compilation message (stderr)

horses.cpp: In member function 'void Aintx::Build(int, int, int)':
horses.cpp:28:61: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   28 |             v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD;
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'void Aintx::setx(int, int, int, int, int)':
horses.cpp:45:61: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   45 |             v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD;
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int Aintx::queryx(int, int, int, int, int)':
horses.cpp:63:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   63 |             return (1LL * ans1 * ans2) % MOD;
      |                    ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int Query()':
horses.cpp:157:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  157 |             return std::max(mx, py);
      |                    ~~~~~~~~^~~~~~~~
horses.cpp:165:81: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  165 |     return (1LL * std::max(mx, py) * aintx.queryx(1, 0, n - 1, 0, pos[sz - 1])) % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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