oj.uz

Submission #712293

# Submission time Handle Problem Language Result Execution time Memory
712293 2023-03-18T14:16:51 Z Nhoksocqt1 Horses (IOI15_horses) C++17
34 / 100
 1500 ms 28420 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;

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

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.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 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 280 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 340 KB Output is correct
20 Correct 1 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 0 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 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 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 1 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 1 ms 340 KB Output is correct
23 Correct 35 ms 340 KB Output is correct
24 Correct 8 ms 340 KB Output is correct
25 Correct 11 ms 340 KB Output is correct
26 Correct 7 ms 440 KB Output is correct
27 Correct 96 ms 340 KB Output is correct
28 Correct 15 ms 340 KB Output is correct
29 Correct 382 ms 444 KB Output is correct
30 Correct 98 ms 416 KB Output is correct
31 Correct 373 ms 408 KB Output is correct
32 Correct 283 ms 404 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1593 ms 24596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
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 1 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 1 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 1 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 37 ms 412 KB Output is correct
24 Correct 8 ms 340 KB Output is correct
25 Correct 11 ms 340 KB Output is correct
26 Correct 8 ms 332 KB Output is correct
27 Correct 100 ms 408 KB Output is correct
28 Correct 12 ms 432 KB Output is correct
29 Correct 377 ms 404 KB Output is correct
30 Correct 103 ms 416 KB Output is correct
31 Correct 363 ms 416 KB Output is correct
32 Correct 305 ms 412 KB Output is correct
33 Execution timed out 1568 ms 28420 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
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 1 ms 340 KB Output is correct
5 Correct 1 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 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 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 1 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 0 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 41 ms 396 KB Output is correct
24 Correct 8 ms 340 KB Output is correct
25 Correct 11 ms 340 KB Output is correct
26 Correct 7 ms 344 KB Output is correct
27 Correct 100 ms 408 KB Output is correct
28 Correct 12 ms 340 KB Output is correct
29 Correct 334 ms 408 KB Output is correct
30 Correct 94 ms 412 KB Output is correct
31 Correct 369 ms 408 KB Output is correct
32 Correct 298 ms 412 KB Output is correct
33 Execution timed out 1552 ms 26828 KB Time limit exceeded
34 Halted 0 ms 0 KB -