oj.uz

답안 #712306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
712306 2023-03-18T14:35:23 Z Nhoksocqt1 말 (IOI15_horses) C++17
34 / 100
 1500 ms 32804 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;

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

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

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

    if(res * (ans % modl) % modl != calc2()) {
        cout << "WRONG ANSWER ! JURY: " << calc2() << ' ' << " FIND: " << res * (ans % modl) % 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) % 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:23:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   23 |             digits[numDigit++] = x % BASE;
      |                                  ~~^~~~~~
horses.cpp: In member function 'Bignum& Bignum::operator*=(int)':
horses.cpp:63:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   63 |             digits[i] = remain % BASE;
      |                         ~~~~~~~^~~~~~
horses.cpp:68:41: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   68 |             digits[numDigit++] = remain % BASE;
      |                                  ~~~~~~~^~~~~~
horses.cpp: In function 'void build(int*, int, int, int, int*)':
horses.cpp:129:16: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  129 | void build(int seg[], int id, int l, int r, int x[]) {
      |            ~~~~^~~~~
horses.cpp:111:4: note: shadowed declaration is here
  111 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'void update(int*, int, int)':
horses.cpp:141:17: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  141 | void update(int seg[], int pos, int val) {
      |             ~~~~^~~~~
horses.cpp:111:4: note: shadowed declaration is here
  111 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int query(int*, int, int, int, int, int)':
horses.cpp:161:15: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  161 | int query(int seg[], int id, int l, int r, int u, int v) {
      |           ~~~~^~~~~
horses.cpp:111:4: note: shadowed declaration is here
  111 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int findFirst(int*, int, int, int, int, int)':
horses.cpp:178:19: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  178 | int findFirst(int seg[], int id, int l, int r, int pos, int k) {
      |               ~~~~^~~~~
horses.cpp:111:4: note: shadowed declaration is here
  111 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int get(int, int, int, int, int)':
horses.cpp:226:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  226 |         return seg[id];
      |                ~~~~~~^
horses.cpp:229:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  229 |     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:257:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  257 |         return seg1[id];
      |                ~~~~~~~^
horses.cpp:260:84: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  260 |     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:285:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  285 |     return res * (ans % modl) % modl;
      |            ~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int calc()':
horses.cpp:334:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  334 |     return res * (ans % modl) % modl;
      |            ~~~~~~~~~~~~~~~~~~~^~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 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 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 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 1 ms 340 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 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 0 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 1 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 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 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 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 9 ms 340 KB Output is correct
24 Correct 8 ms 340 KB Output is correct
25 Correct 8 ms 340 KB Output is correct
26 Correct 7 ms 340 KB Output is correct
27 Correct 19 ms 420 KB Output is correct
28 Correct 9 ms 340 KB Output is correct
29 Correct 27 ms 408 KB Output is correct
30 Correct 15 ms 340 KB Output is correct
31 Correct 31 ms 340 KB Output is correct
32 Correct 34 ms 340 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1571 ms 32784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 360 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 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 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 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
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 10 ms 416 KB Output is correct
24 Correct 8 ms 420 KB Output is correct
25 Correct 9 ms 340 KB Output is correct
26 Correct 8 ms 420 KB Output is correct
27 Correct 18 ms 424 KB Output is correct
28 Correct 9 ms 416 KB Output is correct
29 Correct 30 ms 340 KB Output is correct
30 Correct 15 ms 340 KB Output is correct
31 Correct 32 ms 412 KB Output is correct
32 Correct 29 ms 416 KB Output is correct
33 Execution timed out 1597 ms 32716 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 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 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 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 1 ms 284 KB Output is correct
20 Correct 1 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 11 ms 340 KB Output is correct
24 Correct 7 ms 340 KB Output is correct
25 Correct 8 ms 424 KB Output is correct
26 Correct 8 ms 412 KB Output is correct
27 Correct 19 ms 340 KB Output is correct
28 Correct 10 ms 340 KB Output is correct
29 Correct 28 ms 340 KB Output is correct
30 Correct 14 ms 420 KB Output is correct
31 Correct 32 ms 340 KB Output is correct
32 Correct 29 ms 424 KB Output is correct
33 Execution timed out 1579 ms 32804 KB Time limit exceeded
34 Halted 0 ms 0 KB -