oj.uz

Submission #712290

# Submission time Handle Problem Language Result Execution time Memory
712290 2023-03-18T14:10:53 Z Nhoksocqt1 Horses (IOI15_horses) C++17
17 / 100
 1500 ms 49612 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);
}

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

ll seg[4 * MAXN];
int dp[12][MAXN], 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, 1e2); cout << _X[i] << " \n"[i + 1 == _N];
    }

    for (int i = 0; i < _N; ++i) {
        cin >> _Y[i];
        _Y[i] = Random(1, 1e2); 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, 1e2); 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 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 calc2(void) {
    Bignum prod(1), answer(0);
    for (int i = 1; i <= nArr; ++i) {
        prod *= X[i];
        answer = max(answer, prod * Y[i]);
    }

    return answer % modl;
}

int calc(void) {
    return calc2();

    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

horses.cpp: In function 'void build(int*, int, int, int, int*)':
horses.cpp:92:16: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
   92 | 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:104:17: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  104 | 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:124:15: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  124 | 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:138:19: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  138 | 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:186:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  186 |         return seg[id];
      |                ~~~~~~^
horses.cpp:189:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  189 |     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:234:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  234 |             digits[numDigit++] = x % BASE;
      |                                  ~~^~~~~~
horses.cpp: In member function 'Bignum& Bignum::operator*=(int)':
horses.cpp:274:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  274 |             digits[i] = remain % BASE;
      |                         ~~~~~~~^~~~~~
horses.cpp:279:41: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  279 |             digits[numDigit++] = remain % BASE;
      |                                  ~~~~~~~^~~~~~
horses.cpp: In member function 'std::string Bignum::toString() const':
horses.cpp:323:35: warning: conversion from 'int' to 'char' may change value [-Wconversion]
  323 |                 res.push_back('0' + tmp % 10);
      |                               ~~~~^~~~~~~~~~
horses.cpp: In function 'int calc2()':
horses.cpp:344:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  344 |     return answer % modl;
      |            ~~~~~~~^~~~~~
horses.cpp: In function 'int calc()':
horses.cpp:364:12: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
  364 |         if(prodNow > 1e9) {
      |            ^~~~~~~
horses.cpp:391:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  391 |     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 1 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 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 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 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

Subtask #2
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 1 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 1 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 1 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 1 ms 340 KB Output is correct
16 Correct 1 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 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 717 ms 520 KB Output is correct
24 Correct 395 ms 420 KB Output is correct
25 Execution timed out 1559 ms 416 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 174 ms 49612 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 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 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 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 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 689 ms 460 KB Output is correct
24 Correct 387 ms 412 KB Output is correct
25 Execution timed out 1560 ms 424 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 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 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 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 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 698 ms 388 KB Output is correct
24 Correct 374 ms 532 KB Output is correct
25 Execution timed out 1578 ms 420 KB Time limit exceeded
26 Halted 0 ms 0 KB -