oj.uz

Submission #408947

# Submission time Handle Problem Language Result Execution time Memory
408947 2021-05-19T20:31:00 Z dxz05 Horses (IOI15_horses) C++14
100 / 100
 404 ms 157892 KB 
#include "horses.h"
#include <bits/stdc++.h>

typedef long double ld;
typedef long long ll;

using namespace std;

const int MAXN = 2e6 + 3e2;
const int MOD = 1000000007;

int X[MAXN], Y[MAXN];
int N;

ll powmod(ll n, ll k){
    if (k == 0) return 1;
    ll x = powmod(n, k / 2);
    x = x * x % MOD;
    if (k % 2) x = x * n % MOD;
    return x;
}

struct node{
    ll mult = 1;
    ld mx_sum = 0;
    bool isUpdated = false;
    ll mult_val = 1;
    ld add_val = 0;

    node(ll a1, ld a2, bool a3, ll a4, ld a5){
        mult = a1;
        mx_sum = a2;
        isUpdated = a3;
        mult_val = a4;
        add_val = a5;
    }

    node(){};
};

ll pref_mult[MAXN];
ld pref_sum[MAXN];

node t[MAXN];

void combine(node &par, node lf, node rg){
    if (lf.mx_sum < rg.mx_sum) swap(lf, rg);
    par.mx_sum = lf.mx_sum;
    par.mult = lf.mult;
}

void build(int v = 1, int tl = 0, int tr = N - 1){
    if (tl == tr){
        t[v].mult = pref_mult[tl] * Y[tl] % MOD;
        t[v].mx_sum = pref_sum[tl] + log2(Y[tl]);
        return;
    }
    int tm = (tl + tr) >> 1;
    build(v + v, tl, tm);
    build(v + v + 1, tm + 1, tr);
    combine(t[v], t[v + v], t[v + v + 1]);
}

void propagate(int v, int tl, int tr){
    if (!t[v].isUpdated || tl == tr) return;
    int tm = (tl + tr) >> 1;

    t[v + v].mult = t[v + v].mult * t[v].mult_val % MOD;
    t[v + v].mult_val = t[v + v].mult_val * t[v].mult_val % MOD;

    t[v + v + 1].mult = t[v + v + 1].mult * t[v].mult_val % MOD;
    t[v + v + 1].mult_val = t[v + v + 1].mult_val * t[v].mult_val % MOD;

    t[v + v].mx_sum += t[v].add_val;
    t[v + v + 1].mx_sum += t[v].add_val;

    t[v + v].add_val += t[v].add_val;
    t[v + v + 1].add_val += t[v].add_val;

    combine(t[v], t[v + v], t[v + v + 1]);

    t[v].mult_val = 1;
    t[v].add_val = 0;

    t[v].isUpdated = false;
    t[v + v].isUpdated = t[v + v + 1].isUpdated = true;
}

void update(int l, int r, ll mult, ld add, int v = 1, int tl = 0, int tr = N - 1){
    if (l <= tl && tr <= r){
        t[v].mx_sum += add;
        t[v].add_val += add;
        t[v].mult = t[v].mult * mult % MOD;
        t[v].mult_val = t[v].mult_val * mult % MOD;
        t[v].isUpdated = true;
        return;
    }
    if (tl > r || tr < l) return;

    propagate(v, tl, tr);

    int tm = (tl + tr) >> 1;
    update(l, r, mult, add, v + v, tl, tm);
    update(l, r, mult, add, v + v + 1, tm + 1, tr);

    combine(t[v], t[v + v], t[v + v + 1]);
}

node get(int l, int r, int v = 1, int tl = 0, int tr = N - 1){
    if (l <= tl && tr <= r) return t[v];
    if (tl > r || tr < l) return node(0, 0, 0, 0, 0);

    propagate(v, tl, tr);

    int tm = (tl + tr) >> 1;

    node res, lf = get(l, r, v + v, tl, tm), rg = get(l, r, v + v + 1, tm + 1, tr);
    combine(res, lf, rg);

    return res;
}

int init(int _N, int _X[], int _Y[]) {
    N = _N;
    for (int i = 0; i < N; i++){
        X[i] = _X[i], Y[i] = _Y[i];
        pref_mult[i] = (i > 0 ? pref_mult[i - 1] : 1) * X[i] % MOD;
        pref_sum[i] = (i > 0 ? pref_sum[i - 1] : 0) + log2(X[i]);
    }

    build();

	return get(0, N - 1).mult;
}

int updateX(int pos, int val) {
    ll k = val * powmod(X[pos], MOD - 2) % MOD;
    update(pos, N - 1, k, log2(val) - log2(X[pos]));
    X[pos] = val;
	return get(0, N - 1).mult;
}

int updateY(int pos, int val) {
    ll k = val * powmod(Y[pos], MOD - 2) % MOD;
    update(pos, pos, k, ld(log2(val)) - ld(log2(Y[pos])));
    Y[pos] = val;
	return get(0, N - 1).mult;
}

Compilation message

horses.cpp: In function 'void propagate(int, int, int)':
horses.cpp:66:9: warning: unused variable 'tm' [-Wunused-variable]
   66 |     int tm = (tl + tr) >> 1;
      |         ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:133:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  133 |  return get(0, N - 1).mult;
      |         ~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:140:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  140 |  return get(0, N - 1).mult;
      |         ~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:147:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  147 |  return get(0, N - 1).mult;
      |         ~~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 125508 KB Output is correct
2 Correct 75 ms 125484 KB Output is correct
3 Correct 77 ms 125472 KB Output is correct
4 Correct 74 ms 125476 KB Output is correct
5 Correct 75 ms 125656 KB Output is correct
6 Correct 72 ms 125496 KB Output is correct
7 Correct 74 ms 125512 KB Output is correct
8 Correct 73 ms 125528 KB Output is correct
9 Correct 73 ms 125564 KB Output is correct
10 Correct 72 ms 125500 KB Output is correct
11 Correct 75 ms 125632 KB Output is correct
12 Correct 72 ms 125500 KB Output is correct
13 Correct 73 ms 125508 KB Output is correct
14 Correct 71 ms 125476 KB Output is correct
15 Correct 74 ms 125456 KB Output is correct
16 Correct 72 ms 125508 KB Output is correct
17 Correct 73 ms 125444 KB Output is correct
18 Correct 73 ms 125636 KB Output is correct
19 Correct 71 ms 125508 KB Output is correct
20 Correct 74 ms 125460 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 125536 KB Output is correct
2 Correct 73 ms 125500 KB Output is correct
3 Correct 73 ms 125520 KB Output is correct
4 Correct 74 ms 125464 KB Output is correct
5 Correct 73 ms 125496 KB Output is correct
6 Correct 72 ms 125508 KB Output is correct
7 Correct 75 ms 125504 KB Output is correct
8 Correct 76 ms 125508 KB Output is correct
9 Correct 73 ms 125508 KB Output is correct
10 Correct 75 ms 125456 KB Output is correct
11 Correct 73 ms 125516 KB Output is correct
12 Correct 75 ms 125556 KB Output is correct
13 Correct 75 ms 125492 KB Output is correct
14 Correct 74 ms 125480 KB Output is correct
15 Correct 72 ms 125508 KB Output is correct
16 Correct 73 ms 125524 KB Output is correct
17 Correct 72 ms 125452 KB Output is correct
18 Correct 73 ms 125556 KB Output is correct
19 Correct 73 ms 125532 KB Output is correct
20 Correct 73 ms 125536 KB Output is correct
21 Correct 73 ms 125472 KB Output is correct
22 Correct 74 ms 125540 KB Output is correct
23 Correct 73 ms 125632 KB Output is correct
24 Correct 78 ms 125664 KB Output is correct
25 Correct 73 ms 125628 KB Output is correct
26 Correct 74 ms 125636 KB Output is correct
27 Correct 77 ms 125628 KB Output is correct
28 Correct 81 ms 125564 KB Output is correct
29 Correct 73 ms 125548 KB Output is correct
30 Correct 73 ms 125636 KB Output is correct
31 Correct 75 ms 125508 KB Output is correct
32 Correct 82 ms 125624 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 146140 KB Output is correct
2 Correct 399 ms 157720 KB Output is correct
3 Correct 351 ms 149836 KB Output is correct
4 Correct 380 ms 153744 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 125508 KB Output is correct
2 Correct 74 ms 125508 KB Output is correct
3 Correct 74 ms 125556 KB Output is correct
4 Correct 72 ms 125512 KB Output is correct
5 Correct 73 ms 125548 KB Output is correct
6 Correct 74 ms 125508 KB Output is correct
7 Correct 72 ms 125520 KB Output is correct
8 Correct 72 ms 125532 KB Output is correct
9 Correct 73 ms 125480 KB Output is correct
10 Correct 74 ms 125512 KB Output is correct
11 Correct 77 ms 125564 KB Output is correct
12 Correct 73 ms 125508 KB Output is correct
13 Correct 73 ms 125500 KB Output is correct
14 Correct 74 ms 125560 KB Output is correct
15 Correct 73 ms 125496 KB Output is correct
16 Correct 75 ms 125548 KB Output is correct
17 Correct 72 ms 125492 KB Output is correct
18 Correct 72 ms 125580 KB Output is correct
19 Correct 73 ms 125524 KB Output is correct
20 Correct 73 ms 125516 KB Output is correct
21 Correct 73 ms 125540 KB Output is correct
22 Correct 73 ms 125508 KB Output is correct
23 Correct 75 ms 125544 KB Output is correct
24 Correct 75 ms 125516 KB Output is correct
25 Correct 75 ms 125636 KB Output is correct
26 Correct 82 ms 125596 KB Output is correct
27 Correct 74 ms 125564 KB Output is correct
28 Correct 73 ms 125508 KB Output is correct
29 Correct 74 ms 125552 KB Output is correct
30 Correct 75 ms 125568 KB Output is correct
31 Correct 85 ms 125636 KB Output is correct
32 Correct 75 ms 125600 KB Output is correct
33 Correct 159 ms 145872 KB Output is correct
34 Correct 158 ms 149136 KB Output is correct
35 Correct 172 ms 156088 KB Output is correct
36 Correct 181 ms 156180 KB Output is correct
37 Correct 132 ms 147268 KB Output is correct
38 Correct 146 ms 148168 KB Output is correct
39 Correct 127 ms 147128 KB Output is correct
40 Correct 154 ms 151104 KB Output is correct
41 Correct 133 ms 147256 KB Output is correct
42 Correct 122 ms 147332 KB Output is correct
43 Correct 140 ms 151432 KB Output is correct
44 Correct 140 ms 151468 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 125528 KB Output is correct
2 Correct 79 ms 125492 KB Output is correct
3 Correct 71 ms 125500 KB Output is correct
4 Correct 74 ms 125452 KB Output is correct
5 Correct 73 ms 125508 KB Output is correct
6 Correct 72 ms 125536 KB Output is correct
7 Correct 72 ms 125504 KB Output is correct
8 Correct 72 ms 125516 KB Output is correct
9 Correct 74 ms 125516 KB Output is correct
10 Correct 74 ms 125560 KB Output is correct
11 Correct 76 ms 125456 KB Output is correct
12 Correct 73 ms 125480 KB Output is correct
13 Correct 72 ms 125512 KB Output is correct
14 Correct 73 ms 125448 KB Output is correct
15 Correct 72 ms 125652 KB Output is correct
16 Correct 74 ms 125624 KB Output is correct
17 Correct 79 ms 125556 KB Output is correct
18 Correct 73 ms 125544 KB Output is correct
19 Correct 74 ms 125488 KB Output is correct
20 Correct 73 ms 125468 KB Output is correct
21 Correct 75 ms 125488 KB Output is correct
22 Correct 75 ms 125520 KB Output is correct
23 Correct 75 ms 125656 KB Output is correct
24 Correct 74 ms 125512 KB Output is correct
25 Correct 73 ms 125552 KB Output is correct
26 Correct 75 ms 125552 KB Output is correct
27 Correct 75 ms 125504 KB Output is correct
28 Correct 75 ms 125556 KB Output is correct
29 Correct 75 ms 125600 KB Output is correct
30 Correct 75 ms 125560 KB Output is correct
31 Correct 74 ms 125588 KB Output is correct
32 Correct 73 ms 125520 KB Output is correct
33 Correct 214 ms 148420 KB Output is correct
34 Correct 404 ms 157708 KB Output is correct
35 Correct 354 ms 149896 KB Output is correct
36 Correct 398 ms 153740 KB Output is correct
37 Correct 158 ms 149128 KB Output is correct
38 Correct 158 ms 149064 KB Output is correct
39 Correct 176 ms 156008 KB Output is correct
40 Correct 177 ms 156012 KB Output is correct
41 Correct 136 ms 147296 KB Output is correct
42 Correct 147 ms 148148 KB Output is correct
43 Correct 128 ms 147168 KB Output is correct
44 Correct 154 ms 151108 KB Output is correct
45 Correct 124 ms 147220 KB Output is correct
46 Correct 125 ms 147276 KB Output is correct
47 Correct 141 ms 151460 KB Output is correct
48 Correct 142 ms 151536 KB Output is correct
49 Correct 381 ms 151208 KB Output is correct
50 Correct 384 ms 151100 KB Output is correct
51 Correct 260 ms 157892 KB Output is correct
52 Correct 269 ms 157480 KB Output is correct
53 Correct 310 ms 149496 KB Output is correct
54 Correct 269 ms 150008 KB Output is correct
55 Correct 259 ms 148292 KB Output is correct
56 Correct 272 ms 152944 KB Output is correct
57 Correct 209 ms 148856 KB Output is correct
58 Correct 209 ms 149376 KB Output is correct
59 Correct 147 ms 151496 KB Output is correct