Submission #712339

#	Time	Username	Problem	Language	Result	Execution time	Memory
712339		Nhoksocqt1	Horses (IOI15_horses)	C++17	77 / 100	1545 ms	21620 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 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, 10); 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 findLast(int seg[], int id, int l, int r, int pos, int k) {
    if(seg[id] < k || pos < l)
        return 0;

    if(r <= pos) {
        while(l != r) {
            int mid = (l + r) >> 1;
            if(seg[id << 1 | 1] >= k) {
                id = id << 1 | 1;
                l = mid + 1;
            } else {
                id = id << 1;
                r = mid;
            }
        }

        return l;
    }

    int mid = (l + r) >> 1;
    return max(findLast(seg, id << 1, l, mid, pos, k), findLast(seg, id << 1 | 1, mid + 1, r, pos, k));
}

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

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

    return res;
}

int query(int seg[], int id, int l, int r, int u, int v) {
    if(v < l || u > r)
        return 0;

    if(u <= l && r <= v)
        return seg[id];

    int mid = (l + r) >> 1;
    return max(query(seg, id << 1, l, mid, u, v), query(seg, id << 1 | 1, mid + 1, r, u, v));
}

typedef pair<ll, ll> pll;
int pos[MAXN];

int calc(void) {
    pos[0] = nArr + 1;
    ll prod(1);
    int nPos(0), opt(nArr);
    while(opt > 0 && prod <= 1e9) {
        prod *= X[opt];
        pos[++nPos] = opt;
        opt = findLast(segx, 1, 1, nArr, opt - 1, 2);
    }

    ++nPos, prod = 1;
    pll ansNow = {0, 0};
    ll res = get(opt);
    while(nPos--) {
        int nxt = pos[nPos];
        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;
    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];
        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) {
    ++pos;
    Y[pos] = val;
    update(segy, pos, val);

    return calc();
}

Compilation message (stderr)

horses.cpp: In function 'int get(int)':
horses.cpp:158:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  158 |     return res;
      |            ^~~
horses.cpp: In function 'int calc()':
horses.cpp:179:22: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
  179 |     while(opt > 0 && prod <= 1e9) {
      |                      ^~~~
horses.cpp:8:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
    8 | #define se second
      |            ^
horses.cpp:191:75: note: in expansion of macro 'se'
  191 |         if(!ansNow.se || double(ansNow.fi) / maxY < double(prod) / ansNow.se)
      |                                                                           ^~
horses.cpp:199:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  199 |     return res * ans % modl;
      |            ~~~~~~~~~~^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:218:17: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  218 | int updateX(int pos, int val) {
      |             ~~~~^~~
horses.cpp:173:5: note: shadowed declaration is here
  173 | int pos[MAXN];
      |     ^~~
horses.cpp:220:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  220 |     modify(pos, powermod(X[pos], modl - 2) * val % modl);
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:227:17: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  227 | int updateY(int pos, int val) {
      |             ~~~~^~~
horses.cpp:173:5: note: shadowed declaration is here
  173 | int pos[MAXN];
      |     ^~~

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