Submission #712293

#	Time	Username	Problem	Language	Result	Execution time	Memory
712293		Nhoksocqt1	Horses (IOI15_horses)	C++17	34 / 100	1593 ms	28420 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);
}

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

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

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 query(int seg[], int id, int l, int r, int u, int v) {
    if(u <= l && r <= v)
        return seg[id];

    int mid = (l + r) >> 1, res(0);
    if(mid >= u)
        res = max(res, query(seg, id << 1, l, mid, u, v));

    if(mid < v)
        res = max(res, query(seg, id << 1 | 1, mid + 1, r, u, v));

    return res;
}

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 id, int l, int r, int u, int v) {
    if(v < l || u > r)
        return 1;

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

    int mid = (l + r) >> 1;
    return min(ll(1e9)+1, 1LL * get(id << 1, l, mid, u, v) * get(id << 1 | 1, mid + 1, r, u, v));
}

int calcDP(void) {
    int MAX_HORSE(1);
    for (int i = 1; i <= nArr; ++i)
        MAX_HORSE *= X[i];

    for (int i = 0; i <= nArr; ++i) {
        for (int k = 0; k <= MAX_HORSE; ++k)
            dp[i][k] = -1;
    }

    dp[0][1] = 0;
    for (int i = 0; i < nArr; ++i) {
        for (int k = 0; k <= MAX_HORSE; ++k) {
            if(dp[i][k] < 0)
                continue;

            maximize(dp[i + 1][k * X[i + 1]], dp[i][k]);
        }

        for (int k = MAX_HORSE; k > 0; --k) {
            if(dp[i + 1][k] < 0)
                continue;

            maximize(dp[i + 1][k - 1], dp[i + 1][k] + Y[i + 1]);
        }
    }

    return dp[nArr][0];
}

struct Bignum {
    static const int MAX_DIGIT = 1000;
    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

    string toString(void) const {
        string res;
        for (int i = 0; i < numDigit; ++i) {
            int tmp = digits[i];
            for (int j = 0; j < 9; ++j) {
                res.push_back('0' + tmp % 10);
                tmp /= 10;
            }
        }

        while (res.size() > 1 && res.back() == '0') {
            res.pop_back();
        }

        reverse(res.begin(), res.end());
        return res;
    }
};

int calc(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 l(1), r(nArr), opt(1);
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(get(1, 1, nArr, mid, nArr) > 1e9) {
            opt = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    ll prodNow(1);
    for (int i = opt + 1; i <= nArr; ++i) {
        prodNow *= X[i];
        if(prodNow > 1e9) {
            abort();
        }
    }

    ll res = get(1, 1, nArr, 1, opt), ans(Y[opt]), prod(1);
    while(opt <= nArr) {
        int nxt = findFirst(segx, 1, 1, nArr, opt + 1, 2);
        ans = max(ans, prod * query(segy, 1, 1, nArr, opt, nxt - 1));
        prod *= X[nxt];
        opt = nxt;
    }

    ans %= modl;
    if(res * ans % modl != calc2()) {
        cout << "WRONG ANSWER ! JURY: " << calc2() << ' ' << " FIND: " << res * ans % modl << '\n';
        cout << nArr << '\n';
        for (int i = 1; i <= nArr; ++i)
            cout << X[i] << " \n"[i == nArr];

        for (int i = 1; i <= nArr; ++i)
            cout << Y[i] << " \n"[i == nArr];

        cout << "0\n";
        exit(0);
    }

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

    return calc();
}

int updateX(int pos, int val) {
    ++pos;
    modify(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 function 'void build(int*, int, int, int, int*)':
horses.cpp:42:16: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
   42 | void build(int seg[], int id, int l, int r, int x[]) {
      |            ~~~~^~~~~
horses.cpp:24:4: note: shadowed declaration is here
   24 | ll seg[4 * MAXN];
      |    ^~~
horses.cpp: In function 'void update(int*, int, int)':
horses.cpp:54:17: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
   54 | void update(int seg[], int pos, int val) {
      |             ~~~~^~~~~
horses.cpp:24:4: note: shadowed declaration is here
   24 | ll seg[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int query(int*, int, int, int, int, int)':
horses.cpp:74:15: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
   74 | int query(int seg[], int id, int l, int r, int u, int v) {
      |           ~~~~^~~~~
horses.cpp:24:4: note: shadowed declaration is here
   24 | ll seg[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int findFirst(int*, int, int, int, int, int)':
horses.cpp:88:19: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
   88 | int findFirst(int seg[], int id, int l, int r, int pos, int k) {
      |               ~~~~^~~~~
horses.cpp:24:4: note: shadowed declaration is here
   24 | ll seg[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int get(int, int, int, int, int)':
horses.cpp:136:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  136 |         return seg[id];
      |                ~~~~~~^
horses.cpp:139:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  139 |     return min(ll(1e9)+1, 1LL * get(id << 1, l, mid, u, v) * get(id << 1 | 1, mid + 1, r, u, v));
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In constructor 'Bignum::Bignum(ll)':
horses.cpp:184:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  184 |             digits[numDigit++] = x % BASE;
      |                                  ~~^~~~~~
horses.cpp: In member function 'Bignum& Bignum::operator*=(int)':
horses.cpp:224:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  224 |             digits[i] = remain % BASE;
      |                         ~~~~~~~^~~~~~
horses.cpp:229:41: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  229 |             digits[numDigit++] = remain % BASE;
      |                                  ~~~~~~~^~~~~~
horses.cpp: In member function 'std::string Bignum::toString() const':
horses.cpp:273:35: warning: conversion from 'int' to 'char' may change value [-Wconversion]
  273 |                 res.push_back('0' + tmp % 10);
      |                               ~~~~^~~~~~~~~~
horses.cpp: In function 'int calc()':
horses.cpp:309:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  309 |     return res * (ans % modl) % modl;/*
      |            ~~~~~~~~~~~~~~~~~~~^~~~~~

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