oj.uz

Submission #793820

# Submission time Handle Problem Language Result Execution time Memory
793820 2023-07-26T07:01:29 Z PixelCat Horses (IOI15_horses) C++14
100 / 100
 589 ms 52756 KB 
#ifdef NYAOWO
#include "grader.cpp"
#endif

#include "horses.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 500'000;
const int MOD = 1'000'000'007;
const int INF = 2'000'000'000;

#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
    int a[MAXN * 4 + 10];
    int b[MAXN * 4 + 10];
    void build() {
        fill(a, a + sizeof(a) / sizeof(int), 1);
        fill(b, b + sizeof(b) / sizeof(int), 1);
    }
    void upd(int id, int l, int r, int i, int x) {
        if(l == r) {
            a[id] = x;
            b[id] = x;
            return;
        }
        int m = (l + r) / 2;
        if(i <= m) upd(L(id), l, m, i, x);
        else       upd(R(id), m + 1, r, i, x);
        a[id] = min(INF, a[L(id)] * a[R(id)]);
        b[id] = b[L(id)] * b[R(id)] % MOD;
    }
    int qry(int id, int l, int r, int L, int R) {
        if(l >= L && r <= R) return a[id];
        int m = (l + r) / 2;
        int res = 1;
        if(L <= m) res = min(INF, res * qry(L(id), l, m, L, R));
        if(R > m)  res = min(INF, res * qry(R(id), m + 1, r, L, R));
        return res;
    }
    int qry_mod(int id, int l, int r, int L, int R) {
        if(l >= L && r <= R) return b[id];
        int m = (l + r) / 2;
        int res = 1;
        if(L <= m) res *= qry_mod(L(id), l, m, L, R);
        if(R > m)  res *= qry_mod(R(id), m + 1, r, L, R);
        return res % MOD;
    }
} seg;

int n;
int x[MAXN + 10];
int y[MAXN + 10];

struct SegTree2 {
    bool smol(const int &a, const int &b) {
        if(a == b) return false;
        if(a > b) return !smol(b, a);
        return y[a] < seg.qry(0, 0, n - 1, a + 1, b) * y[b];
    }
    int zzzz(const int &a, const int &b) {
        if(smol(a, b)) return b;
        return a;
    }
    int mx[MAXN * 4 + 10];
    void build(int id, int l, int r) {
        if(l == r) {
            mx[id] = l;
            return;
        }
        int m = (l + r) / 2;
        build(L(id), l, m);
        build(R(id), m + 1, r);
        mx[id] = zzzz(mx[L(id)], mx[R(id)]);
    }
    void upd(int id, int l, int r, int i) {
        if(l == r) return;
        int m = (l + r) / 2;
        if(i <= m) upd(L(id), l, m, i);
        else       upd(R(id), m + 1, r, i);
        mx[id] = zzzz(mx[L(id)], mx[R(id)]);
    }
} uwu;

int32_t eval(int pos) {
    return (int32_t)(y[pos] * seg.qry_mod(0, 0, n - 1, 0, pos) % MOD);
}
int32_t solve() {
    int pos = uwu.mx[0];
    return eval(pos);
}

int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
    n = N;
    seg.build();
    For(i, 0, n - 1) {
        x[i] = X[i];
        seg.upd(0, 0, n - 1, i, x[i]);
    }
    For(i, 0, n - 1) {
        y[i] = Y[i];
    }
    uwu.build(0, 0, n - 1);
    return solve();
}

int32_t updateX(int32_t pos, int32_t val) {	
    x[pos] = val;
    seg.upd(0, 0, n - 1, pos, val);
    uwu.upd(0, 0, n - 1, pos);
    // uwu.build(0, 0, n - 1);
    return solve();
}

int32_t updateY(int32_t pos, int32_t val) {
    y[pos] = val;
    uwu.upd(0, 0, n - 1, pos);
    // uwu.build(0, 0, n - 1);
    return solve();
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31576 KB Output is correct
2 Correct 13 ms 31612 KB Output is correct
3 Correct 17 ms 31572 KB Output is correct
4 Correct 15 ms 31560 KB Output is correct
5 Correct 13 ms 31572 KB Output is correct
6 Correct 13 ms 31572 KB Output is correct
7 Correct 13 ms 31588 KB Output is correct
8 Correct 13 ms 31572 KB Output is correct
9 Correct 13 ms 31612 KB Output is correct
10 Correct 13 ms 31620 KB Output is correct
11 Correct 15 ms 31572 KB Output is correct
12 Correct 12 ms 31572 KB Output is correct
13 Correct 16 ms 31556 KB Output is correct
14 Correct 14 ms 31536 KB Output is correct
15 Correct 16 ms 31572 KB Output is correct
16 Correct 12 ms 31632 KB Output is correct
17 Correct 13 ms 31588 KB Output is correct
18 Correct 14 ms 31632 KB Output is correct
19 Correct 12 ms 31528 KB Output is correct
20 Correct 12 ms 31612 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31572 KB Output is correct
2 Correct 12 ms 31568 KB Output is correct
3 Correct 12 ms 31600 KB Output is correct
4 Correct 14 ms 31620 KB Output is correct
5 Correct 12 ms 31572 KB Output is correct
6 Correct 12 ms 31572 KB Output is correct
7 Correct 13 ms 31592 KB Output is correct
8 Correct 16 ms 31572 KB Output is correct
9 Correct 15 ms 31620 KB Output is correct
10 Correct 13 ms 31548 KB Output is correct
11 Correct 14 ms 31604 KB Output is correct
12 Correct 13 ms 31636 KB Output is correct
13 Correct 13 ms 31524 KB Output is correct
14 Correct 13 ms 31620 KB Output is correct
15 Correct 13 ms 31612 KB Output is correct
16 Correct 13 ms 31572 KB Output is correct
17 Correct 12 ms 31568 KB Output is correct
18 Correct 12 ms 31572 KB Output is correct
19 Correct 12 ms 31572 KB Output is correct
20 Correct 16 ms 31512 KB Output is correct
21 Correct 13 ms 31608 KB Output is correct
22 Correct 14 ms 31616 KB Output is correct
23 Correct 16 ms 31572 KB Output is correct
24 Correct 13 ms 31572 KB Output is correct
25 Correct 16 ms 31584 KB Output is correct
26 Correct 14 ms 31640 KB Output is correct
27 Correct 13 ms 31572 KB Output is correct
28 Correct 13 ms 31568 KB Output is correct
29 Correct 14 ms 31572 KB Output is correct
30 Correct 14 ms 31568 KB Output is correct
31 Correct 14 ms 31612 KB Output is correct
32 Correct 14 ms 31572 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 52476 KB Output is correct
2 Correct 418 ms 52604 KB Output is correct
3 Correct 425 ms 52572 KB Output is correct
4 Correct 456 ms 52672 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31548 KB Output is correct
2 Correct 13 ms 31616 KB Output is correct
3 Correct 13 ms 31532 KB Output is correct
4 Correct 12 ms 31568 KB Output is correct
5 Correct 12 ms 31556 KB Output is correct
6 Correct 13 ms 31520 KB Output is correct
7 Correct 13 ms 31636 KB Output is correct
8 Correct 13 ms 31588 KB Output is correct
9 Correct 12 ms 31592 KB Output is correct
10 Correct 13 ms 31616 KB Output is correct
11 Correct 13 ms 31572 KB Output is correct
12 Correct 13 ms 31620 KB Output is correct
13 Correct 12 ms 31628 KB Output is correct
14 Correct 13 ms 31564 KB Output is correct
15 Correct 12 ms 31572 KB Output is correct
16 Correct 12 ms 31572 KB Output is correct
17 Correct 13 ms 31560 KB Output is correct
18 Correct 13 ms 31572 KB Output is correct
19 Correct 13 ms 31572 KB Output is correct
20 Correct 12 ms 31592 KB Output is correct
21 Correct 12 ms 31572 KB Output is correct
22 Correct 12 ms 31508 KB Output is correct
23 Correct 14 ms 31684 KB Output is correct
24 Correct 13 ms 31664 KB Output is correct
25 Correct 16 ms 31620 KB Output is correct
26 Correct 13 ms 31572 KB Output is correct
27 Correct 15 ms 31584 KB Output is correct
28 Correct 13 ms 31572 KB Output is correct
29 Correct 15 ms 31576 KB Output is correct
30 Correct 14 ms 31572 KB Output is correct
31 Correct 13 ms 31668 KB Output is correct
32 Correct 13 ms 31564 KB Output is correct
33 Correct 211 ms 51620 KB Output is correct
34 Correct 190 ms 51732 KB Output is correct
35 Correct 182 ms 51760 KB Output is correct
36 Correct 173 ms 51788 KB Output is correct
37 Correct 188 ms 51696 KB Output is correct
38 Correct 164 ms 51748 KB Output is correct
39 Correct 165 ms 51704 KB Output is correct
40 Correct 168 ms 51792 KB Output is correct
41 Correct 161 ms 51752 KB Output is correct
42 Correct 165 ms 51776 KB Output is correct
43 Correct 168 ms 51644 KB Output is correct
44 Correct 150 ms 51684 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31520 KB Output is correct
2 Correct 12 ms 31572 KB Output is correct
3 Correct 12 ms 31572 KB Output is correct
4 Correct 12 ms 31572 KB Output is correct
5 Correct 17 ms 31572 KB Output is correct
6 Correct 12 ms 31528 KB Output is correct
7 Correct 13 ms 31620 KB Output is correct
8 Correct 12 ms 31616 KB Output is correct
9 Correct 13 ms 31608 KB Output is correct
10 Correct 12 ms 31572 KB Output is correct
11 Correct 13 ms 31572 KB Output is correct
12 Correct 16 ms 31568 KB Output is correct
13 Correct 12 ms 31608 KB Output is correct
14 Correct 12 ms 31572 KB Output is correct
15 Correct 13 ms 31516 KB Output is correct
16 Correct 12 ms 31572 KB Output is correct
17 Correct 13 ms 31572 KB Output is correct
18 Correct 12 ms 31604 KB Output is correct
19 Correct 13 ms 31572 KB Output is correct
20 Correct 12 ms 31516 KB Output is correct
21 Correct 12 ms 31536 KB Output is correct
22 Correct 12 ms 31616 KB Output is correct
23 Correct 14 ms 31572 KB Output is correct
24 Correct 13 ms 31572 KB Output is correct
25 Correct 13 ms 31588 KB Output is correct
26 Correct 13 ms 31572 KB Output is correct
27 Correct 14 ms 31604 KB Output is correct
28 Correct 13 ms 31576 KB Output is correct
29 Correct 14 ms 31572 KB Output is correct
30 Correct 14 ms 31572 KB Output is correct
31 Correct 14 ms 31564 KB Output is correct
32 Correct 14 ms 31624 KB Output is correct
33 Correct 283 ms 52556 KB Output is correct
34 Correct 373 ms 52708 KB Output is correct
35 Correct 429 ms 52508 KB Output is correct
36 Correct 412 ms 52620 KB Output is correct
37 Correct 193 ms 51684 KB Output is correct
38 Correct 189 ms 51676 KB Output is correct
39 Correct 178 ms 51788 KB Output is correct
40 Correct 174 ms 51708 KB Output is correct
41 Correct 186 ms 51736 KB Output is correct
42 Correct 155 ms 51684 KB Output is correct
43 Correct 165 ms 51712 KB Output is correct
44 Correct 166 ms 51908 KB Output is correct
45 Correct 162 ms 51752 KB Output is correct
46 Correct 167 ms 51760 KB Output is correct
47 Correct 151 ms 51608 KB Output is correct
48 Correct 150 ms 51692 KB Output is correct
49 Correct 571 ms 52640 KB Output is correct
50 Correct 544 ms 52568 KB Output is correct
51 Correct 325 ms 52660 KB Output is correct
52 Correct 247 ms 52676 KB Output is correct
53 Correct 589 ms 52756 KB Output is correct
54 Correct 304 ms 52468 KB Output is correct
55 Correct 387 ms 51912 KB Output is correct
56 Correct 347 ms 52664 KB Output is correct
57 Correct 349 ms 52616 KB Output is correct
58 Correct 400 ms 52628 KB Output is correct
59 Correct 149 ms 51628 KB Output is correct