Submission #712282

#	Time	Username	Problem	Language	Result	Execution time	Memory
712282		Nhoksocqt1	Horses (IOI15_horses)	C++17	17 / 100	1548 ms	24900 KiB

horses

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

int calc2(void) {
    ll 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) {
    ll prodNow(1), opt(nArr);
    while(opt > 1 && prodNow <= 1e9) {
        prodNow *= X[opt];
        --opt;
    }

    while(opt > 0 && X[opt] == 1)
        --opt;

    ll res(1), ans(1);
    for (int i = 1; i <= opt; ++i)
        res = res * X[i] % modl;

    ll prod(1);
    while(opt <= nArr) {
        ans = max(ans, prod * Y[opt]);
        prod *= X[++opt];
    }

    ans %= modl;
    return res * ans % 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 (stderr)

horses.cpp: In function 'void build(int*, int, int, int, int*)':
horses.cpp:93:16: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
   93 | void build(int seg[], int id, int l, int r, int x[]) {
      |            ~~~~^~~~~
horses.cpp:25:4: note: shadowed declaration is here
   25 | ll seg[4 * MAXN];
      |    ^~~
horses.cpp: In function 'void update(int*, int, int)':
horses.cpp:105:17: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  105 | void update(int seg[], int pos, int val) {
      |             ~~~~^~~~~
horses.cpp:25:4: note: shadowed declaration is here
   25 | ll seg[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int query(int*, int, int, int, int, int)':
horses.cpp:125:15: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  125 | int query(int seg[], int id, int l, int r, int u, int v) {
      |           ~~~~^~~~~
horses.cpp:25:4: note: shadowed declaration is here
   25 | ll seg[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int findFirst(int*, int, int, int, int, int)':
horses.cpp:139:19: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  139 | int findFirst(int seg[], int id, int l, int r, int pos, int k) {
      |               ~~~~^~~~~
horses.cpp:25:4: note: shadowed declaration is here
   25 | ll seg[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int get(int, int, int, int, int)':
horses.cpp:187:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  187 |         return seg[id];
      |                ~~~~~~^
horses.cpp:190:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  190 |     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 calc2()':
horses.cpp:230:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  230 |     return answer % modl;
      |            ~~~~~~~^~~~~~
horses.cpp: In function 'int calc()':
horses.cpp:235:22: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
  235 |     while(opt > 1 && prodNow <= 1e9) {
      |                      ^~~~~~~
horses.cpp:254:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  254 |     return res * ans % modl;/*
      |            ~~~~~~~~~~^~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23