oj.uz

Submission #712327

# Submission time Handle Problem Language Result Execution time Memory
712327 2023-03-18T15:01:28 Z Nhoksocqt1 Horses (IOI15_horses) C++17
100 / 100
 1461 ms 40704 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 3 ms 340 KB Output is correct
24 Correct 3 ms 340 KB Output is correct
25 Correct 3 ms 340 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 7 ms 340 KB Output is correct
28 Correct 4 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 3 ms 384 KB Output is correct
31 Correct 3 ms 424 KB Output is correct
32 Correct 6 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1222 ms 34048 KB Output is correct
2 Correct 642 ms 33972 KB Output is correct
3 Correct 671 ms 33780 KB Output is correct
4 Correct 751 ms 33836 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 3 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 3 ms 340 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 7 ms 340 KB Output is correct
28 Correct 3 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 3 ms 340 KB Output is correct
31 Correct 3 ms 340 KB Output is correct
32 Correct 6 ms 340 KB Output is correct
33 Correct 208 ms 32844 KB Output is correct
34 Correct 207 ms 32972 KB Output is correct
35 Correct 239 ms 32828 KB Output is correct
36 Correct 220 ms 32844 KB Output is correct
37 Correct 297 ms 32856 KB Output is correct
38 Correct 216 ms 32804 KB Output is correct
39 Correct 165 ms 32840 KB Output is correct
40 Correct 218 ms 32780 KB Output is correct
41 Correct 215 ms 32880 KB Output is correct
42 Correct 250 ms 32832 KB Output is correct
43 Correct 175 ms 32684 KB Output is correct
44 Correct 178 ms 32752 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 280 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 3 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 3 ms 340 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 8 ms 420 KB Output is correct
28 Correct 3 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 3 ms 340 KB Output is correct
31 Correct 4 ms 340 KB Output is correct
32 Correct 5 ms 340 KB Output is correct
33 Correct 1197 ms 33788 KB Output is correct
34 Correct 638 ms 33784 KB Output is correct
35 Correct 672 ms 33792 KB Output is correct
36 Correct 738 ms 33860 KB Output is correct
37 Correct 209 ms 32844 KB Output is correct
38 Correct 205 ms 32848 KB Output is correct
39 Correct 239 ms 32844 KB Output is correct
40 Correct 220 ms 32768 KB Output is correct
41 Correct 297 ms 32844 KB Output is correct
42 Correct 220 ms 32808 KB Output is correct
43 Correct 166 ms 32764 KB Output is correct
44 Correct 217 ms 32892 KB Output is correct
45 Correct 206 ms 32888 KB Output is correct
46 Correct 254 ms 32956 KB Output is correct
47 Correct 173 ms 32676 KB Output is correct
48 Correct 171 ms 32764 KB Output is correct
49 Correct 661 ms 33868 KB Output is correct
50 Correct 623 ms 33832 KB Output is correct
51 Correct 714 ms 33756 KB Output is correct
52 Correct 602 ms 33840 KB Output is correct
53 Correct 1461 ms 33964 KB Output is correct
54 Correct 793 ms 37788 KB Output is correct
55 Correct 284 ms 35848 KB Output is correct
56 Correct 665 ms 40704 KB Output is correct
57 Correct 653 ms 36500 KB Output is correct
58 Correct 1108 ms 37272 KB Output is correct
59 Correct 177 ms 39244 KB Output is correct