Submission #309385

#	Time	Username	Problem	Language	Result	Execution time	Memory
309385		mihai145	Horses (IOI15_horses)	C++14	17 / 100	772 ms	48888 KiB

horses

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

///set pe platouri pe X => rangeuri de forma F 1 1 1 ... 1
///in ficare set tinem: l, r, F, maxY

///arbore de intervale peste Y
///update Y => update in arborele de intervale

///arbore de intervale peste X
///update X => update in arborele de intervale

///update X => 4 cazuri:
///1) nicio modificare
///2) un F > 1 devine 1 => unim intervalul curent cu cel din stanga
///2) un F = 1 devine >1 => separam intervalul curent in 2 intervale mai mici
///3) un F > 1 se modifica => modificam F in setul respectiv

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

struct Interval {
    int st, dr;
    int f, maxy;

    bool operator < (const Interval other) const {
        return st < other.st;
    }
};

std::set < Interval > s;

int Query()
{
    auto p = s.rbegin();

    std::vector <int> xs;
    std::vector <int> ys;
    std::vector <std::pair <int, int>> segments;

    int seenSegments = 0;
    long long xProd = 1LL;
    while(true)
        {
            Interval i = *p;
            --p;

            xProd *= i.f;
            if(xProd > YMAX)
                {
                    xs.push_back(i.f);
                    ys.push_back(i.maxy);
                    segments.push_back({i.st, i.dr});
                    break;
                }

            xs.push_back(i.f);
            ys.push_back(i.maxy);
            segments.push_back({i.st, i.dr});

            seenSegments++;
            if(seenSegments == (int)s.size())
                break;
        }

    reverse(xs.begin(), xs.end());
    reverse(ys.begin(), ys.end());
    reverse(segments.begin(), segments.end());

    long long currX = 1LL, currMaxProd = 1LL;
    std::pair <int, int> maxSegment;

    for(int i = 0; i < (int)xs.size(); i++)
        {
            currX *= xs[i];

            if(1LL * currX * ys[i] > currMaxProd)
                {
                    currMaxProd = 1LL * currX * ys[i];
                    maxSegment = segments[i];
                }
        }

    return (1LL * aintx.queryx(1, 0, n - 1, 0, maxSegment.second) * ainty.queryy(1, 0, n - 1, maxSegment.first, maxSegment.second)) % 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);

    int l = 0, factor = x[0];
    for(int r = 1; r < n; r++)
        if(x[r] > 1)
            {
                Interval i;

                i.st = l;
                i.dr = r - 1;
                i.f = factor;

                i.maxy = ainty.queryy(1, 0, n - 1, l, r - 1);

                s.insert(i);

                l = r;
                factor = x[r];
            }

    Interval i;
    i.st = l;
    i.dr = n - 1;
    i.f = factor;

    i.maxy = ainty.queryy(1, 0, n - 1, l, n - 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);
    x[pos] = val;

    auto p = s.upper_bound({pos, 0, 0, 0});
    Interval bef = *(--p);

    if(x[pos] > 1 && val == 1)
        {
            Interval bef_bef = *(--p);

            Interval merged;

            merged.st = bef_bef.st;
            merged.dr = bef.dr;
            merged.f = bef_bef.f;
            merged.maxy = ainty.queryy(1, 0, n - 1, merged.st, merged.dr);

            s.erase(bef);
            s.erase(bef_bef);
            s.insert(merged);
        }
    else if(x[pos] == 1 && val > 1)
        {
            Interval split1, split2;

            split1.st = bef.st;
            split1.dr = pos - 1;
            split1.f = bef.f;
            split1.maxy = ainty.queryy(1, 0, n - 1, bef.st, pos - 1);

            split2.st = pos;
            split2.dr = bef.dr;
            split2.f = val;
            split2.maxy = ainty.queryy(1, 0, n - 1, pos, bef.dr);

            s.erase(bef);
            s.insert(split1);
            s.insert(split2);
        }
    else
        {
            s.erase(bef);

            bef.f = val;
            s.insert(bef);
        }

	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;

    auto p = s.upper_bound({pos, 0, 0, 0});
    Interval bef = *(--p);

    s.erase(bef);
    s.insert({bef.st, bef.dr, bef.f, ainty.queryy(1, 0, n - 1, bef.st, bef.dr)});

	return Query();
}

Compilation message (stderr)

horses.cpp: In member function 'void Aintx::Build(int, int, int)':
horses.cpp:43:61: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   43 |             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:60:61: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   60 |             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:75:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   75 |             return (1LL * ans1 * ans2) % MOD;
      |                    ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int Query()':
horses.cpp:195:133: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  195 |     return (1LL * aintx.queryx(1, 0, n - 1, 0, maxSegment.second) * ainty.queryy(1, 0, n - 1, maxSegment.first, maxSegment.second)) % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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