Submission #712215

#	Time	Username	Problem	Language	Result	Execution time	Memory
712215		Nhoksocqt1	말 (IOI15_horses)	C++17	37 / 100	639 ms	28820 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 fen[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, 1e9); cout << _X[i] << " \n"[i + 1 == _N];
    }

    for (int i = 0; i < _N; ++i) {
        cin >> _Y[i];
        _Y[i] = Random(1, 1e9); 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, 1e9); 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;
}

void modify(int i, int v) {
    for (; i > 0; i -= i & -i)
        fen[i] = fen[i] * v % modl;
}

int get(int i) {
    ll res(1);
    for (; i <= nArr; i += i & -i)
        res = res * fen[i] % modl;

    return res;
}

int getx(int i) {
    ll res(1);
    for (; i <= nArr; i += i & -i)
        res = min(ll(1e9)+1, res * fen[i]);

    return res;
}

int query(int u, int v) {
    return 1LL * get(u) * powermod(get(v + 1), modl - 2) % modl;
}

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)
        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 res(nArr + 1);
    int mid = (l + r) >> 1;
    if(mid >= pos)
        res = min(res, findFirst(seg, id << 1, l, mid, pos, k));

    res = min(res, findFirst(seg, id << 1 | 1, mid + 1, r, pos, k));
    return res;
}

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 calc(void) {
    int l(1), r(nArr), opt(1);
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(getx(mid) > 1e9) {
            opt = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    ll res = query(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;
    }

    /*if(res * ans != calcDP()) {
        cout << "WRONG ANSWER ! JURY: " << calcDP() << ' ' << " FIND: " << res * ans << '\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];
        fen[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, powermod(X[pos], modl - 2) * val % modl);
    update(segx, pos, val);

    X[pos] = val;
    return calc();
}

int updateY(int pos, int val) {
    Y[++pos] = val;
    update(segy, pos, val);

    return calc();
}

Compilation message (stderr)

horses.cpp: In function 'int get(int)':
horses.cpp:101:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  101 |     return res;
      |            ^~~
horses.cpp: In function 'int getx(int)':
horses.cpp:109:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  109 |     return res;
      |            ^~~
horses.cpp: In function 'int query(int, int)':
horses.cpp:113:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  113 |     return 1LL * get(u) * powermod(get(v + 1), modl - 2) % modl;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int calc()':
horses.cpp:247:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  247 |     return res * (ans % modl) % modl;
      |            ~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:268:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  268 |     modify(pos, powermod(X[pos], modl - 2) * val % modl);
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~

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