oj.uz

Submission #712324

# Submission time Handle Problem Language Result Execution time Memory
712324 2023-03-18T14:50:44 Z Nhoksocqt1 Horses (IOI15_horses) C++17
77 / 100
 1500 ms 35712 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;

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 > v)
        return 0;

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

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;
}

typedef pair<ll, ll> pll;

int calc(void) {
    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;
        }
    }

    --opt;
    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;
    /*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]), 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:33:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   33 |             digits[numDigit++] = x % BASE;
      |                                  ~~^~~~~~
horses.cpp: In member function 'Bignum& Bignum::operator*=(int)':
horses.cpp:73:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   73 |             digits[i] = remain % BASE;
      |                         ~~~~~~~^~~~~~
horses.cpp:78:41: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   78 |             digits[numDigit++] = remain % BASE;
      |                                  ~~~~~~~^~~~~~
horses.cpp: In function 'void build(int*, int, int, int, int*)':
horses.cpp:139:16: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  139 | void build(int seg[], int id, int l, int r, int x[]) {
      |            ~~~~^~~~~
horses.cpp:121:4: note: shadowed declaration is here
  121 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'void update(int*, int, int)':
horses.cpp:151:17: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  151 | void update(int seg[], int pos, int val) {
      |             ~~~~^~~~~
horses.cpp:121:4: note: shadowed declaration is here
  121 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int query(int*, int, int, int, int, int)':
horses.cpp:171:15: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  171 | int query(int seg[], int id, int l, int r, int u, int v) {
      |           ~~~~^~~~~
horses.cpp:121:4: note: shadowed declaration is here
  121 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int findFirst(int*, int, int, int, int, int)':
horses.cpp:188:19: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  188 | int findFirst(int seg[], int id, int l, int r, int pos, int k) {
      |               ~~~~^~~~~
horses.cpp:121:4: note: shadowed declaration is here
  121 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int get(int, int, int, int, int)':
horses.cpp:236:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  236 |         return seg[id];
      |                ~~~~~~^
horses.cpp:239:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  239 |     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 function 'int get1(int, int, int, int, int)':
horses.cpp:267:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  267 |         return seg1[id];
      |                ~~~~~~~^
horses.cpp:270:84: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  270 |     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:295:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  295 |     return res * (ans % modl) % modl;
      |            ~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int calc()':
horses.cpp:7:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
    7 | #define se second
      |            ^
horses.cpp:329:75: note: in expansion of macro 'se'
  329 |         if(!ansNow.se || double(ansNow.fi) / maxY < double(prod) / ansNow.se)
      |                                                                           ^~
horses.cpp:350:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  350 |     return res * ans % modl;
      |            ~~~~~~~~~~^~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 312 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 308 KB Output is correct
7 Correct 1 ms 312 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 1 ms 340 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 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 0 ms 340 KB Output is correct
19 Correct 1 ms 316 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 1 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 312 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 312 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 312 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 312 KB Output is correct
15 Correct 1 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 1 ms 316 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 316 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 460 KB Output is correct
26 Correct 3 ms 340 KB Output is correct
27 Correct 7 ms 332 KB Output is correct
28 Correct 4 ms 340 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 4 ms 436 KB Output is correct
31 Correct 6 ms 340 KB Output is correct
32 Correct 7 ms 328 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1320 ms 35712 KB Output is correct
2 Correct 844 ms 35016 KB Output is correct
3 Correct 824 ms 34764 KB Output is correct
4 Correct 922 ms 34756 KB Output is correct

Subtask #4
23.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 312 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 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 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 312 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 316 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 3 ms 440 KB Output is correct
24 Correct 3 ms 340 KB Output is correct
25 Correct 3 ms 340 KB Output is correct
26 Correct 3 ms 340 KB Output is correct
27 Correct 9 ms 324 KB Output is correct
28 Correct 4 ms 340 KB Output is correct
29 Correct 2 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 5 ms 340 KB Output is correct
33 Correct 236 ms 33280 KB Output is correct
34 Correct 228 ms 33420 KB Output is correct
35 Correct 254 ms 33388 KB Output is correct
36 Correct 238 ms 33368 KB Output is correct
37 Correct 312 ms 33380 KB Output is correct
38 Correct 230 ms 33300 KB Output is correct
39 Correct 192 ms 33288 KB Output is correct
40 Correct 236 ms 33304 KB Output is correct
41 Correct 221 ms 33308 KB Output is correct
42 Correct 258 ms 33360 KB Output is correct
43 Correct 177 ms 33312 KB Output is correct
44 Correct 178 ms 33288 KB Output is correct

Subtask #5
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 320 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 312 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 1 ms 316 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 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 1 ms 340 KB Output is correct
18 Correct 1 ms 320 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 3 ms 340 KB Output is correct
24 Correct 3 ms 332 KB Output is correct
25 Correct 4 ms 460 KB Output is correct
26 Correct 3 ms 340 KB Output is correct
27 Correct 7 ms 324 KB Output is correct
28 Correct 3 ms 340 KB Output is correct
29 Correct 2 ms 428 KB Output is correct
30 Correct 3 ms 340 KB Output is correct
31 Correct 4 ms 328 KB Output is correct
32 Correct 6 ms 340 KB Output is correct
33 Correct 1285 ms 34828 KB Output is correct
34 Correct 812 ms 34256 KB Output is correct
35 Correct 846 ms 34252 KB Output is correct
36 Correct 940 ms 34284 KB Output is correct
37 Correct 235 ms 33384 KB Output is correct
38 Correct 271 ms 33356 KB Output is correct
39 Correct 253 ms 33300 KB Output is correct
40 Correct 247 ms 33460 KB Output is correct
41 Correct 311 ms 33392 KB Output is correct
42 Correct 247 ms 33480 KB Output is correct
43 Correct 207 ms 33448 KB Output is correct
44 Correct 262 ms 33296 KB Output is correct
45 Correct 232 ms 33388 KB Output is correct
46 Correct 262 ms 33396 KB Output is correct
47 Correct 183 ms 33296 KB Output is correct
48 Correct 176 ms 33228 KB Output is correct
49 Correct 849 ms 34300 KB Output is correct
50 Correct 816 ms 34440 KB Output is correct
51 Correct 906 ms 34288 KB Output is correct
52 Correct 773 ms 34252 KB Output is correct
53 Execution timed out 1576 ms 34284 KB Time limit exceeded
54 Halted 0 ms 0 KB -