Submission #212256

#	Time	Username	Problem	Language	Result	Execution time	Memory
212256		apostoldaniel854	Horses (IOI15_horses)	C++14	0 / 100	399 ms	50296 KiB

horses

#include <horses.h>
#include <bits/stdc++.h>

using namespace std;


struct RangeSeg {
    int startRange;
    int endRange;
    int bestY;
    bool operator < (RangeSeg const &other) const {
        return startRange < other.startRange;
    }
};


set <RangeSeg> Intervals;

const int MOD = 1e9 + 7, MAX_N = 5e5;

int N;
int X[1 + MAX_N];
int Y[1 + MAX_N];


struct Bit {
    vector <int> aib;
    int n;

    int lsb (int x) {
        return x & -x;
    }

    void init (int _n) {
        n = _n;
        aib.resize (n + 1, 1);
    }
    void upd (int pos, int val) {
        while (pos <= n) {
            aib[pos] = (1ll * aib[pos] * val) % MOD;
            pos += lsb (pos);
        }
    }
    int qry (int pos) {
        int ans = 1;
        while (pos) {
            ans = (1ll * ans * aib[pos]) % MOD;
            pos -= lsb (pos);
        }
        return ans;
    }
};

struct SegMax {
    vector <int> seg;
    int n;

    int query (int node, int l, int r, int nl, int nr) {
        if (nl <= l && r <= nr)
            return seg[node];
        int mid = (l + r) / 2;
        int ans = 0;
        if (mid >= nl)
            ans = max (ans, query (2 * node, l, mid, nl, nr));
        if (mid < nr)
            ans = max (ans, query (2 * node + 1, mid + 1, r, nl, nr));
        return ans;
    }
    void update (int node, int l, int r, int pos, int val) {
        if (l == r) {
            seg[node] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (mid >= pos)
            update (2 * node, l, mid, pos, val);
        else
            update (2 * node + 1, mid + 1, r, pos, val);
        seg[node] = max (seg[2 * node], seg[2 * node + 1]);
    }

    void init (int _n) {
        n = _n;
        seg.resize (4 * n + 1, 0);
    }
    void updateVal (int pos, int val) {
        update (1, 1, n, pos, val);
    }
    int queryRange (int l, int r) {
        return query (1, 1, n, l, r);
    }
};
SegMax MaxY;
Bit aibMOD;
const int MAGIC = 30;

typedef long double ld;
typedef long long ll;

const ld EPS = 1e-12;

int getAns () {
    int NoSeg = 0;
    auto it = Intervals.end ();
    it = prev (it);
    ll xTot = 1;
    ll bestX = 0;
    int bestY = 0;
    int bestMOD = 0;
    while (NoSeg < min (MAGIC, (int) Intervals.size ())) {
        RangeSeg x = *it;
        /// bestY / xTot > best
        if (bestMOD == 0 || (1ll * x.bestY * bestX > 1ll * bestY * xTot)) {
            bestX = xTot;
            bestY = x.bestY;
            bestMOD = 1ll * aibMOD.qry (x.startRange) * x.bestY % MOD;
        }
        xTot *= X[x.startRange];
        if (xTot > (1ll << 30))
            return bestMOD;
        it = prev (it);
        NoSeg++;
    }
    return bestMOD;
}





int lgput (int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1)
            ans = 1ll * ans * a % MOD;
        a = 1ll * a * a % MOD;
        b /= 2;
    }
    return ans;
}

int inv (int x) {
    return lgput (x, MOD - 2);
}

void split (set <RangeSeg>::iterator it, int pos) {
    RangeSeg x = *it;
    if (pos == x.startRange) return;
    Intervals.erase (it);
    RangeSeg x1 = {x.startRange, pos - 1, MaxY.queryRange (x.startRange, pos - 1)},
             x2 = {pos, x.endRange, MaxY.queryRange (pos, x.endRange)};
    Intervals.insert (x1);
    Intervals.insert (x2);
}

void join (set <RangeSeg>::iterator it1, set <RangeSeg>::iterator it2) {
    RangeSeg x1 = *it1,
             x2 = *it2;
    Intervals.erase (it1);
    Intervals.erase (it2);
    RangeSeg x = {x1.startRange, x2.endRange, MaxY.queryRange (x1.startRange, x2.endRange)};
    Intervals.insert (x);
}

int updateX (int pos, int val) {
    aibMOD.upd (pos, inv (X[pos]));
    aibMOD.upd (pos, val);
    if (val == 1) {
        if (X[pos] != 1) {
            set <RangeSeg>::iterator it2 = Intervals.lower_bound ({pos, 0, 0});
            if (it2 != Intervals.begin ()) {
                set <RangeSeg>::iterator it1 = prev (it2);
                join (it1, it2);
            }
        }
    }
    else {
        if (X[pos] == 1) {
            set <RangeSeg>::iterator it = Intervals.lower_bound ({pos + 1, 0, 0});
            it = prev (it);
            split (it, pos);
        }
    }
    X[pos] = val;
    return getAns ();
}

int updateY (int pos, int val) {
    MaxY.updateVal (pos, val);
    set <RangeSeg>::iterator it = Intervals.lower_bound ({pos + 1, 0, 0});
    it = prev (it);
    /// why???
    auto x = *it;
    Intervals.erase (it);
    x.bestY = MaxY.queryRange (x.startRange, x.endRange);
    Intervals.insert (x);
    return getAns ();
}

int init (int n, int x[], int y[]) {
    N = n;
    for (int i = 1; i <= N; i++)
        X[i] = x[i], Y[i] = y[i];

    MaxY.init (N);
    for (int i = 1; i <= N; i++)
        MaxY.updateVal (i, Y[i]);

    aibMOD.init (N);
    int startIndex = 1;
    for (int i = 1; i <= N; i++) {
        aibMOD.upd (i, X[i]);
        if (X[i] > 1) {
            if (i > 1)
                Intervals.insert ({startIndex, i - 1, MaxY.queryRange (startIndex, i - 1)});
            startIndex = i;
        }
    }
    Intervals.insert ({startIndex, n, MaxY.queryRange (startIndex, n)});

   // for (auto x : Intervals) {
  //      cout << x.startRange << " " << x.endRange << " " << x.bestY << "\n";
 //   }
    return getAns ();
}

/**
5
1 2 1 1 2
2 3 4 5 6
4
2 3 20
1 2 1
2 3 1
1 3 5
**/

/*int x[1 + MAX_N], y[1 + MAX_N];
int main () {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 1; i <= n; i++)
        cin >> y[i];
    cout << init (n, x, y) << "\n";
    int m;
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int pos, val, type;
        cin >> type >> pos >> val;
        if (type == 1)
            cout << updateX (pos, val) << "\n";
        else
            cout << updateY (pos, val) << "\n";
    }

    return 0;
}*/

Compilation message (stderr)

horses.cpp: In member function 'void Bit::upd(int, int)':
horses.cpp:40:47: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'long long int' may alter its value [-Wconversion]
             aib[pos] = (1ll * aib[pos] * val) % MOD;
                        ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int Bit::qry(int)':
horses.cpp:47:42: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             ans = (1ll * ans * aib[pos]) % MOD;
                   ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int getAns()':
horses.cpp:116:65: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             bestMOD = 1ll * aibMOD.qry (x.startRange) * x.bestY % MOD;
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int lgput(int, int)':
horses.cpp:135:33: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             ans = 1ll * ans * a % MOD;
                   ~~~~~~~~~~~~~~^~~~~
horses.cpp:136:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         a = 1ll * a * a % MOD;
             ~~~~~~~~~~~~^~~~~

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