Submission #712327

#	Time	Username	Problem	Language	Result	Execution time	Memory
712327		Nhoksocqt1	Horses (IOI15_horses)	C++17	100 / 100	1461 ms	40704 KiB

horses

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

struct Bignum {
    static const int MAX_DIGIT = 5;
    static const int BASE = (int) 1e9;
    int digits[MAX_DIGIT], numDigit;

    Bignum(ll x = 0) {
        numDigit = 0;
        memset(digits, 0, sizeof digits);

        if (!x) numDigit = 1;

        while (x > 0) {
            digits[numDigit++] = x % BASE;
            x /= BASE;
        }
    }

    Bignum& operator += (const Bignum &x) {
        int carry(0);
        numDigit = max(numDigit, x.numDigit);

        for (int i = 0; i < numDigit; ++i) {
            digits[i] += x.digits[i] + carry;

            if (digits[i] >= BASE) {
                digits[i] -= BASE;
                carry = 1;
            } else {
                carry = 0;
            }
        }

        if (carry)
            digits[numDigit++] = carry;

        return *this;
    }

    Bignum operator + (const Bignum &x) const {
        Bignum res(*this);
        return res += x;
    }

    Bignum& operator *= (int x) {
        if (!x) {
            *this = Bignum(0);
            return *this;
        }

        ll remain = 0;
        for (int i = 0; i < numDigit; ++i) {
            remain += 1LL * digits[i] * x;
            digits[i] = remain % BASE;
            remain /= BASE;
        }

        while (remain > 0) {
            digits[numDigit++] = remain % BASE;
            remain /= BASE;
        }

        return *this;
    }

    Bignum operator * (int x) const {
        Bignum res(*this);
        res *= x;
        return res;
    }

    ll operator % (ll x) const {
		ll res(0);
		for (int i = numDigit - 1; i >= 0; i--)
            res = (res * BASE + digits[i]) % x;

		return res;
	}

    #define COMPARE(a, b) (((a) > (b)) - ((a) < (b)))
    int compare(const Bignum &x) const {
        if (numDigit != x.numDigit) {
            return COMPARE(numDigit, x.numDigit);
        }

        for (int i = numDigit - 1; i >= 0; --i) {
            if (digits[i] != x.digits[i]) {
                return COMPARE(digits[i], x.digits[i]);
            }
        }
        return 0;
    }

    #define DEF_OPER(o) bool operator o (const Bignum &x) const { return compare(x) o 0; }
    DEF_OPER(<) DEF_OPER(>) DEF_OPER(>=) DEF_OPER(<=) DEF_OPER(==) DEF_OPER(!=)
    #undef DEF_OPER
};

const int MAXN = 500005;
const int modl = 1e9+7;

ll seg[4 * MAXN], seg1[4 * MAXN];
int X[MAXN], Y[MAXN], nArr;

#ifdef Nhoksocqt1

int init(int _N, int _X[], int _Y[]);

int updateX(int pos, int val);

int updateY(int pos, int val);

int _X[MAXN], _Y[MAXN];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    freopen("HORSES.inp", "r", stdin);
    freopen("HORSES.out", "w", stdout);

    int _N;
    cin >> _N;

    for (int i = 0; i < _N; ++i) {
        cin >> _X[i];
        //_X[i] = Random(1, 1e9); cout << _X[i] << " \n"[i + 1 == _N];
    }

    for (int i = 0; i < _N; ++i) {
        cin >> _Y[i];
        //_Y[i] = Random(1, 1e9); cout << _Y[i] << " \n"[i + 1 == _N];
    }

    cout << init(_N, _X, _Y) << '\n';

    int Q;
    cin >> Q;
    while(Q--) {
        int type, pos, val;
        cin >> type >> pos >> val;
        type = Random(0, 1), pos = Random(0, _N - 1), val = Random(1, 1e9); cout << type << ' ' << pos << ' ' << val << '\n';

        if(type == 0) {
            cout << updateX(pos, val) << '\n';
        } else {
            cout << updateY(pos, val) << '\n';
        }
    }

    return 0;
}

#endif // Nhoksocqt1

ll powermod(ll a, int exponent) {
    ll res(1);
    while(exponent > 0) {
        if(exponent & 1)
            res = res * a % modl;

        a = a * a % modl;
        exponent >>= 1;
    }

    return res;
}

int segx[4 * MAXN], segy[4 * MAXN];

void build(int seg[], int id, int l, int r, int x[]) {
    if(l == r) {
        seg[id] = x[l];
        return;
    }

    int mid = (l + r) >> 1;
    build(seg, id << 1, l, mid, x);
    build(seg, id << 1 | 1, mid + 1, r, x);
    seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}

void update(int seg[], int pos, int val) {
    int id(1), l(1), r(nArr);
    while(l != r) {
        int mid = (l + r) >> 1;
        if(pos <= mid) {
            id = id << 1;
            r = mid;
        } else {
            id = id << 1 | 1;
            l = mid + 1;
        }
    }

    seg[id] = val;
    while(id > 1) {
        id >>= 1;
        seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
    }
}

int findFirst(int seg[], int id, int l, int r, int pos, int k) {
    if(seg[id] < k || pos > r)
        return nArr + 1;

    if(pos <= l) {
        while(l != r) {
            int mid = (l + r) >> 1;
            if(seg[id << 1] < k) {
                id = id << 1 | 1;
                l = mid + 1;
            } else {
                id = id << 1;
                r = mid;
            }
        }

        return l;
    }

    int mid = (l + r) >> 1;
    return min(findFirst(seg, id << 1, l, mid, pos, k), findFirst(seg, id << 1 | 1, mid + 1, r, pos, k));
}

void modify(int pos, int val) {
    int id(1), l(1), r(nArr);
    while(l != r) {
        int mid = (l + r) >> 1;
        if(pos <= mid) {
            id = id << 1;
            r = mid;
        } else {
            id = id << 1 | 1;
            l = mid + 1;
        }
    }

    seg[id] = val;
    while(id > 1) {
        id >>= 1;
        seg[id] = min(ll(1e9)+1, 1LL * seg[id << 1] * seg[id << 1 | 1]);
    }
}

int get(int k) {
    ll prod(1);
    int id(1), l(1), r(nArr);
    while(l != r) {
        int mid = (l + r) >> 1;
        if(prod * seg[id << 1 | 1] < k) {
            prod *= seg[id << 1 | 1];
            id = id << 1;
            r = mid;
        } else {
            id = id << 1 | 1;
            l = mid + 1;
        }
    }

    return l;
}

void modify1(int pos, int val) {
    int id(1), l(1), r(nArr);
    while(l != r) {
        int mid = (l + r) >> 1;
        if(pos <= mid) {
            id = id << 1;
            r = mid;
        } else {
            id = id << 1 | 1;
            l = mid + 1;
        }
    }

    seg1[id] = val;
    while(id > 1) {
        id >>= 1;
        seg1[id] = 1LL * seg1[id << 1] * seg1[id << 1 | 1] % modl;
    }
}

int get1(int id, int l, int r, int u, int v) {
    if(v < l || u > r)
        return 1;

    if(u <= l && r <= v)
        return seg1[id];

    int mid = (l + r) >> 1;
    return 1LL * get1(id << 1, l, mid, u, v) * get1(id << 1 | 1, mid + 1, r, u, v) % modl;
}

int calc2(void) {
    Bignum prodNow(1);
    int opt(nArr);
    while(opt > 0 && prodNow <= 1e9) {
        prodNow *= X[opt];
        --opt;
    }

    while(opt > 0 && X[opt] == 1)
        --opt;

    ll res(1);
    Bignum ans(1);
    for (int i = 1; i <= opt; ++i)
        res = res * X[i] % modl;

    Bignum prod(1);
    while(opt <= nArr) {
        ans = max(ans, prod * Y[opt]);
        prod *= X[++opt];
    }

    return res * (ans % modl) % modl;
}

int query(int seg[], int id, int l, int r, int u, int v) {
    if(v < l || u > r)
        return 0;

    if(u <= l && r <= v)
        return seg[id];

    int mid = (l + r) >> 1;
    return max(query(seg, id << 1, l, mid, u, v), query(seg, id << 1 | 1, mid + 1, r, u, v));
}

typedef pair<ll, ll> pll;

int calc(void) {
    int opt = get(int(1e9)+1) - 1;
    int l = 1, r = opt;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(query(segx, 1, 1, nArr, mid, opt) == 1) {
            opt = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    pll ansNow = {0, 0};
    ll res = (opt == 0) ? 1 : get1(1, 1, nArr, 1, opt), prod(1);
    while(opt <= nArr) {
        int nxt = findFirst(segx, 1, 1, nArr, opt + 1, 2);
        int maxY = query(segy, 1, 1, nArr, max(1, opt), nxt - 1);
        if(!ansNow.se || double(ansNow.fi) / maxY < double(prod) / ansNow.se)
            ansNow = {prod, maxY};

        prod *= X[nxt];
        opt = nxt;
    }

    ll ans = ansNow.fi % modl * ansNow.se % modl;
    return res * ans % modl;
}

int init(int _N, int _X[], int _Y[]) {
    nArr = _N;
    for (int i = 1; i <= nArr; ++i) {
        X[i] = _X[i - 1];
        Y[i] = _Y[i - 1];
    }

    build(segx, 1, 1, nArr, X);
    build(segy, 1, 1, nArr, Y);
    for (int i = 1; i <= nArr; ++i)
        modify(i, X[i]), modify1(i, X[i]);

    return calc();
}

int updateX(int pos, int val) {
    ++pos;
    modify(pos, val);
    modify1(pos, val);
    update(segx, pos, val);

    X[pos] = val;
    return calc();
}

int updateY(int pos, int val) {
    ++pos;
    Y[pos] = val;
    update(segy, pos, val);

    return calc();
}

Compilation message (stderr)

horses.cpp: In constructor 'Bignum::Bignum(ll)':
horses.cpp:34:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   34 |             digits[numDigit++] = x % BASE;
      |                                  ~~^~~~~~
horses.cpp: In member function 'Bignum& Bignum::operator*=(int)':
horses.cpp:74:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   74 |             digits[i] = remain % BASE;
      |                         ~~~~~~~^~~~~~
horses.cpp:79:41: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   79 |             digits[numDigit++] = remain % BASE;
      |                                  ~~~~~~~^~~~~~
horses.cpp: In function 'void build(int*, int, int, int, int*)':
horses.cpp:190:16: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  190 | void build(int seg[], int id, int l, int r, int x[]) {
      |            ~~~~^~~~~
horses.cpp:122:4: note: shadowed declaration is here
  122 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'void update(int*, int, int)':
horses.cpp:202:17: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  202 | void update(int seg[], int pos, int val) {
      |             ~~~~^~~~~
horses.cpp:122:4: note: shadowed declaration is here
  122 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int findFirst(int*, int, int, int, int, int)':
horses.cpp:222:19: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  222 | int findFirst(int seg[], int id, int l, int r, int pos, int k) {
      |               ~~~~^~~~~
horses.cpp:122:4: note: shadowed declaration is here
  122 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int get1(int, int, int, int, int)':
horses.cpp:308:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  308 |         return seg1[id];
      |                ~~~~~~~^
horses.cpp:311:84: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  311 |     return 1LL * get1(id << 1, l, mid, u, v) * get1(id << 1 | 1, mid + 1, r, u, v) % modl;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int calc2()':
horses.cpp:336:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  336 |     return res * (ans % modl) % modl;
      |            ~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int query(int*, int, int, int, int, int)':
horses.cpp:339:15: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  339 | int query(int seg[], int id, int l, int r, int u, int v) {
      |           ~~~~^~~~~
horses.cpp:122:4: note: shadowed declaration is here
  122 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int calc()':
horses.cpp:8:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
    8 | #define se second
      |            ^
horses.cpp:370:75: note: in expansion of macro 'se'
  370 |         if(!ansNow.se || double(ansNow.fi) / maxY < double(prod) / ansNow.se)
      |                                                                           ^~
horses.cpp:378:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  378 |     return res * ans % modl;
      |            ~~~~~~~~~~^~~~~~

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