oj.uz

Submission #712339

# Submission time Handle Problem Language Result Execution time Memory
712339 2023-03-18T15:31:32 Z Nhoksocqt1 Horses (IOI15_horses) C++17
77 / 100
 1500 ms 21620 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);
}

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

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.0 / 17.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 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 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 316 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 312 KB Output is correct
19 Correct 1 ms 340 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 0 ms 340 KB Output is correct
2 Correct 1 ms 316 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 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 1 ms 340 KB Output is correct
10 Correct 1 ms 312 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 308 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 312 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 316 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 3 ms 320 KB Output is correct
26 Correct 1 ms 324 KB Output is correct
27 Correct 6 ms 340 KB Output is correct
28 Correct 3 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 2 ms 412 KB Output is correct
31 Correct 4 ms 408 KB Output is correct
32 Correct 6 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1404 ms 21384 KB Output is correct
2 Correct 227 ms 21272 KB Output is correct
3 Correct 296 ms 21188 KB Output is correct
4 Correct 380 ms 21172 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 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 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 308 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 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 308 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 2 ms 328 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 3 ms 340 KB Output is correct
26 Correct 2 ms 324 KB Output is correct
27 Correct 7 ms 324 KB Output is correct
28 Correct 3 ms 328 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 2 ms 340 KB Output is correct
31 Correct 4 ms 340 KB Output is correct
32 Correct 6 ms 340 KB Output is correct
33 Correct 77 ms 20612 KB Output is correct
34 Correct 66 ms 20616 KB Output is correct
35 Correct 102 ms 20568 KB Output is correct
36 Correct 83 ms 20516 KB Output is correct
37 Correct 205 ms 20684 KB Output is correct
38 Correct 94 ms 20540 KB Output is correct
39 Correct 52 ms 20592 KB Output is correct
40 Correct 90 ms 20532 KB Output is correct
41 Correct 93 ms 20568 KB Output is correct
42 Correct 122 ms 20536 KB Output is correct
43 Correct 56 ms 20440 KB Output is correct
44 Correct 55 ms 20496 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 312 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 308 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 312 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 312 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 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 2 ms 340 KB Output is correct
24 Correct 2 ms 412 KB Output is correct
25 Correct 3 ms 340 KB Output is correct
26 Correct 2 ms 324 KB Output is correct
27 Correct 7 ms 340 KB Output is correct
28 Correct 3 ms 340 KB Output is correct
29 Correct 2 ms 320 KB Output is correct
30 Correct 2 ms 328 KB Output is correct
31 Correct 4 ms 340 KB Output is correct
32 Correct 6 ms 340 KB Output is correct
33 Correct 1312 ms 21620 KB Output is correct
34 Correct 220 ms 21408 KB Output is correct
35 Correct 320 ms 21552 KB Output is correct
36 Correct 421 ms 21524 KB Output is correct
37 Correct 77 ms 20512 KB Output is correct
38 Correct 62 ms 20560 KB Output is correct
39 Correct 110 ms 20580 KB Output is correct
40 Correct 85 ms 20524 KB Output is correct
41 Correct 198 ms 20708 KB Output is correct
42 Correct 118 ms 20620 KB Output is correct
43 Correct 59 ms 20500 KB Output is correct
44 Correct 84 ms 20592 KB Output is correct
45 Correct 94 ms 20616 KB Output is correct
46 Correct 132 ms 20620 KB Output is correct
47 Correct 60 ms 20528 KB Output is correct
48 Correct 70 ms 20496 KB Output is correct
49 Correct 325 ms 21552 KB Output is correct
50 Correct 229 ms 21492 KB Output is correct
51 Correct 440 ms 21484 KB Output is correct
52 Correct 204 ms 21452 KB Output is correct
53 Execution timed out 1545 ms 21496 KB Time limit exceeded
54 Halted 0 ms 0 KB -