oj.uz

Submission #1005306

# Submission time Handle Problem Language Result Execution time Memory
1005306 2024-06-22T10:11:24 Z coolboy19521 Horses (IOI15_horses) C++17
34 / 100
 131 ms 74316 KB 
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#include "horses.h"
#define ld float
#define i64 long long
 
using namespace std;
 
const i64 sz = 5e5 + 25;
const i64 md = 1e9 + 7;
 
i64 lz1m[sz * 4], lz1d[sz * 4];
i64 st1[sz * 4];
ld lz2m[sz * 4], lz2d[sz * 4];
pair<ld, i64> st2[sz * 4];
ld d[sz];
i64 a[sz], b[sz], c[sz];
i64 n;
 
i64 bp(i64 x, i64 b) {
    if (0 == b) return 1;
    i64 r = bp(x, b / 2) % md;
    r = (r * r) % md;
    if (b % 2) return (r * x) % md;
    return r;
}
 
void build1(i64 le, i64 ri, i64 v) {
    lz1m[v] = 1;
    lz1d[v] = 1;
    if (le == ri) {
        st1[v] = c[le] * b[le] % md;
        return;
    }
    i64 mi = (le + ri) / 2;
    build1(le, mi, v * 2);
    build1(mi + 1, ri, v * 2 + 1);
    st1[v] = (st1[v * 2] + st1[v * 2 + 1]) % md;
}
 
void relax1(i64 v, i64 le, i64 ri) {
    if (lz1m[v] != 1 || lz1d[v] != 1) {
        st1[v] = (st1[v] * lz1m[v]) % md;
        st1[v] = (st1[v] * bp(lz1d[v], md - 2)) % md;
        if (le != ri) {
            lz1m[v * 2] = (lz1m[v * 2] * lz1m[v]) % md;
            lz1m[v * 2 + 1] = (lz1m[v * 2 + 1] * lz1m[v]) % md;
            lz1d[v * 2] = (lz1d[v * 2] * lz1d[v]) % md;
            lz1d[v * 2 + 1] = (lz1d[v * 2 + 1] * lz1d[v]) % md;
        }
        lz1m[v] = 1;
        lz1d[v] = 1;
    }
}
 
void rupdate1(i64 le, i64 ri, i64 ql, i64 qr, i64 v, i64 m, i64 d) {
    relax1(v, le, ri);
    if (le > qr || ri < ql) return;
    if (ql <= le && ri <= qr) {
        lz1m[v] = (lz1m[v] * m) % md;
        lz1d[v] = (lz1d[v] * d) % md;
        relax1(v, le, ri);
        return;
    }
    i64 mi = (le + ri) / 2;
    rupdate1(le, mi, ql, qr, v * 2, m, d);
    rupdate1(mi + 1, ri, ql, qr, v * 2 + 1, m, d);
    st1[v] = (st1[v * 2] + st1[v * 2 + 1]) % md;
}
 
void pupdate1(i64 le, i64 ri, i64 ix, i64 v, i64 m, i64 d) {
    relax1(v, le, ri);
    if (le > ix || ri < ix) return;
    if (le == ix && ix == ri) {
        st1[v] = (st1[v] * m) % md;
        st1[v] = (st1[v] * bp(d, md - 2)) % md;
        return;
    }
    i64 mi = (le + ri) / 2;
    pupdate1(le, mi, ix, v * 2, m, d);
    pupdate1(mi + 1, ri, ix, v * 2 + 1, m, d);
    st1[v] = (st1[v * 2] + st1[v * 2 + 1]) % md;
}
 
i64 query1(i64 le, i64 ri, i64 ix, i64 v) {
    relax1(v, le, ri);
    if (le > ix || ri < ix) return 0;
    if (le == ix && ix == ri) {
        return st1[v] % md;
    }
    i64 mi = (le + ri) / 2;
    i64 lq = query1(le, mi, ix, v * 2);
    i64 rq = query1(mi + 1, ri, ix, v * 2 + 1);
    return (lq + rq) % md;
}
 
pair<ld, i64> marj(i64 v) {
    auto& le = st2[v * 2];
    auto& ri = st2[v * 2 + 1];
    if (le.first >= ri.first) {
        return le;
    }
    return ri;
}
 
void build2(i64 le, i64 ri, i64 v) {
    if (le == ri) {
        st2[v] = make_pair(d[le] + log10(b[le]), le);
        return;
    }
    i64 mi = (le + ri) / 2;
    build2(le, mi, v * 2);
    build2(mi + 1, ri, v * 2 + 1);
    st2[v] = marj(v);
}
 
void relax2(i64 v, i64 le, i64 ri) {
    if (lz2m[v] != 0 || lz2d[v] != 0) {
        st2[v].first += lz2m[v];
        st2[v].first -= lz2d[v];
        if (le != ri) {
            lz2m[v * 2] += lz2m[v];
            lz2m[v * 2 + 1] += lz2m[v];
            lz2d[v * 2] += lz2d[v];
            lz2d[v * 2 + 1] += lz2d[v];
        }
        lz2m[v] = 0;
        lz2d[v] = 0;
    }
}
 
void rupdate2(i64 le, i64 ri, i64 ql, i64 qr, i64 v, ld m, ld d) {
    relax2(v, le, ri);
    if (le > qr || ri < ql) return;
    if (ql <= le && ri <= qr) {
        lz2m[v] += m;
        lz2d[v] += d;
        relax2(v, le, ri);
        return;
    }
    i64 mi = (le + ri) / 2;
    rupdate2(le, mi, ql, qr, v * 2, m, d);
    rupdate2(mi + 1, ri, ql, qr, v * 2 + 1, m, d);
    st2[v] = marj(v);
}
 
void pupdate2(i64 le, i64 ri, i64 ix, i64 v, ld m, ld d) {
    relax2(v, le, ri);
    if (le > ix || ri < ix) return;
    if (le == ix && ri == ix) {
        st2[v].first += m;
        st2[v].first -= d;
        return;
    }
    i64 mi = (le + ri) / 2;
    pupdate2(le, mi, ix, v * 2, m, d);
    pupdate2(mi + 1, ri, ix, v * 2 + 1, m, d);
    st2[v] = marj(v);
}
 
int init(int N, int x[], int y[]) {
    n = N;
    c[0] = 1;
    d[0] = 0;
 
    for (i64 i = 1; i <= n; i++) {
        a[i] = x[i - 1];
        b[i] = y[i - 1];
        c[i] = c[i - 1] * a[i] % md;
        d[i] = d[i - 1] + log10(a[i]);
    }
 
    build1(1, n, 1);
    build2(1, n, 1);
 
    i64 ix = st2[1].second;
 
    return query1(1, n, ix, 1);
}
 
int updateX(int pos, int val) {
    pos++;
    rupdate1(1, n, pos, n, 1, val, a[pos]);
    rupdate2(1, n, pos, n, 1, log10(val), log10(a[pos]));
    a[pos] = val;
    relax2(1, 1, n);
    i64 ix = st2[1].second;
 
    return query1(1, n, ix, 1);
}
 
int updateY(int pos, int val) {
    pos++;
    pupdate1(1, n, pos, 1, val, b[pos]);
    pupdate2(1, n, pos, 1, log10(val), log10(b[pos]));
    b[pos] = val;
    relax2(1, 1, n);
    i64 ix = st2[1].second;
 
    return query1(1, n, ix, 1);
}

Compilation message

horses.cpp: In function 'long long int bp(long long int, long long int)':
horses.cpp:20:19: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   20 | i64 bp(i64 x, i64 b) {
      |                   ^
horses.cpp:17:12: note: shadowed declaration is here
   17 | i64 a[sz], b[sz], c[sz];
      |            ^
horses.cpp: In function 'void rupdate1(long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
horses.cpp:56:65: warning: declaration of 'd' shadows a global declaration [-Wshadow]
   56 | void rupdate1(i64 le, i64 ri, i64 ql, i64 qr, i64 v, i64 m, i64 d) {
      |                                                                 ^
horses.cpp:16:4: note: shadowed declaration is here
   16 | ld d[sz];
      |    ^
horses.cpp: In function 'void pupdate1(long long int, long long int, long long int, long long int, long long int, long long int)':
horses.cpp:71:57: warning: declaration of 'd' shadows a global declaration [-Wshadow]
   71 | void pupdate1(i64 le, i64 ri, i64 ix, i64 v, i64 m, i64 d) {
      |                                                         ^
horses.cpp:16:4: note: shadowed declaration is here
   16 | ld d[sz];
      |    ^
horses.cpp: In function 'void rupdate2(long long int, long long int, long long int, long long int, long long int, float, float)':
horses.cpp:132:63: warning: declaration of 'd' shadows a global declaration [-Wshadow]
  132 | void rupdate2(i64 le, i64 ri, i64 ql, i64 qr, i64 v, ld m, ld d) {
      |                                                               ^
horses.cpp:16:4: note: shadowed declaration is here
   16 | ld d[sz];
      |    ^
horses.cpp: In function 'void pupdate2(long long int, long long int, long long int, long long int, float, float)':
horses.cpp:147:55: warning: declaration of 'd' shadows a global declaration [-Wshadow]
  147 | void pupdate2(i64 le, i64 ri, i64 ix, i64 v, ld m, ld d) {
      |                                                       ^
horses.cpp:16:4: note: shadowed declaration is here
   16 | ld d[sz];
      |    ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:170:25: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'float' may change value [-Wfloat-conversion]
  170 |         d[i] = d[i - 1] + log10(a[i]);
      |                ~~~~~~~~~^~~~~~~~~~~~~
horses.cpp:178:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  178 |     return query1(1, n, ix, 1);
      |            ~~~~~~^~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:184:36: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'float' may change value [-Wfloat-conversion]
  184 |     rupdate2(1, n, pos, n, 1, log10(val), log10(a[pos]));
      |                               ~~~~~^~~~~
horses.cpp:184:48: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'float' may change value [-Wfloat-conversion]
  184 |     rupdate2(1, n, pos, n, 1, log10(val), log10(a[pos]));
      |                                           ~~~~~^~~~~~~~
horses.cpp:189:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  189 |     return query1(1, n, ix, 1);
      |            ~~~~~~^~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:195:33: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'float' may change value [-Wfloat-conversion]
  195 |     pupdate2(1, n, pos, 1, log10(val), log10(b[pos]));
      |                            ~~~~~^~~~~
horses.cpp:195:45: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'float' may change value [-Wfloat-conversion]
  195 |     pupdate2(1, n, pos, 1, log10(val), log10(b[pos]));
      |                                        ~~~~~^~~~~~~~
horses.cpp:200:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  200 |     return query1(1, n, ix, 1);
      |            ~~~~~~^~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 1 ms 14684 KB Output is correct
4 Correct 1 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 1 ms 14684 KB Output is correct
7 Correct 1 ms 14684 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 1 ms 14684 KB Output is correct
11 Correct 1 ms 14684 KB Output is correct
12 Correct 1 ms 14684 KB Output is correct
13 Correct 1 ms 14684 KB Output is correct
14 Correct 1 ms 14684 KB Output is correct
15 Correct 2 ms 14684 KB Output is correct
16 Correct 1 ms 14684 KB Output is correct
17 Correct 1 ms 14680 KB Output is correct
18 Correct 1 ms 14684 KB Output is correct
19 Correct 1 ms 14684 KB Output is correct
20 Correct 1 ms 14680 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 14684 KB Output is correct
2 Correct 1 ms 14684 KB Output is correct
3 Correct 1 ms 14684 KB Output is correct
4 Correct 1 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 1 ms 14684 KB Output is correct
7 Correct 1 ms 14680 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 1 ms 14684 KB Output is correct
11 Correct 2 ms 14684 KB Output is correct
12 Correct 1 ms 14684 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 2 ms 14684 KB Output is correct
15 Correct 2 ms 14684 KB Output is correct
16 Correct 1 ms 14684 KB Output is correct
17 Correct 2 ms 14684 KB Output is correct
18 Correct 1 ms 14684 KB Output is correct
19 Correct 2 ms 14680 KB Output is correct
20 Correct 1 ms 14684 KB Output is correct
21 Correct 2 ms 14684 KB Output is correct
22 Correct 2 ms 14684 KB Output is correct
23 Correct 5 ms 14684 KB Output is correct
24 Correct 5 ms 14684 KB Output is correct
25 Correct 3 ms 14680 KB Output is correct
26 Correct 5 ms 14684 KB Output is correct
27 Correct 4 ms 14684 KB Output is correct
28 Correct 5 ms 14684 KB Output is correct
29 Correct 7 ms 14856 KB Output is correct
30 Correct 7 ms 14684 KB Output is correct
31 Correct 3 ms 14684 KB Output is correct
32 Correct 3 ms 14684 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 66900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 14684 KB Output is correct
2 Correct 1 ms 14684 KB Output is correct
3 Correct 1 ms 14680 KB Output is correct
4 Correct 1 ms 14684 KB Output is correct
5 Correct 1 ms 14684 KB Output is correct
6 Correct 1 ms 14684 KB Output is correct
7 Correct 1 ms 14764 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 14680 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 1 ms 14684 KB Output is correct
12 Correct 1 ms 14684 KB Output is correct
13 Correct 1 ms 14684 KB Output is correct
14 Correct 1 ms 14684 KB Output is correct
15 Correct 2 ms 14684 KB Output is correct
16 Correct 1 ms 14684 KB Output is correct
17 Correct 1 ms 14684 KB Output is correct
18 Correct 1 ms 14788 KB Output is correct
19 Correct 1 ms 14684 KB Output is correct
20 Correct 2 ms 14680 KB Output is correct
21 Correct 2 ms 14684 KB Output is correct
22 Correct 1 ms 14684 KB Output is correct
23 Correct 5 ms 14684 KB Output is correct
24 Correct 5 ms 14684 KB Output is correct
25 Correct 2 ms 14684 KB Output is correct
26 Correct 3 ms 14684 KB Output is correct
27 Correct 3 ms 14684 KB Output is correct
28 Correct 4 ms 14684 KB Output is correct
29 Correct 6 ms 14684 KB Output is correct
30 Correct 6 ms 14864 KB Output is correct
31 Correct 2 ms 14684 KB Output is correct
32 Correct 3 ms 14684 KB Output is correct
33 Incorrect 131 ms 74316 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 1 ms 14684 KB Output is correct
3 Correct 1 ms 14684 KB Output is correct
4 Correct 1 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 1 ms 14684 KB Output is correct
7 Correct 1 ms 14684 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 1 ms 14684 KB Output is correct
10 Correct 1 ms 14684 KB Output is correct
11 Correct 2 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 1 ms 14684 KB Output is correct
14 Correct 1 ms 14684 KB Output is correct
15 Correct 2 ms 14684 KB Output is correct
16 Correct 2 ms 14788 KB Output is correct
17 Correct 2 ms 14684 KB Output is correct
18 Correct 2 ms 14936 KB Output is correct
19 Correct 2 ms 14684 KB Output is correct
20 Correct 2 ms 14684 KB Output is correct
21 Correct 1 ms 14684 KB Output is correct
22 Correct 1 ms 14684 KB Output is correct
23 Correct 5 ms 14684 KB Output is correct
24 Correct 5 ms 14860 KB Output is correct
25 Correct 3 ms 14684 KB Output is correct
26 Correct 4 ms 14684 KB Output is correct
27 Correct 5 ms 14784 KB Output is correct
28 Correct 5 ms 14768 KB Output is correct
29 Correct 8 ms 14684 KB Output is correct
30 Correct 7 ms 14684 KB Output is correct
31 Correct 2 ms 14684 KB Output is correct
32 Correct 3 ms 14684 KB Output is correct
33 Incorrect 106 ms 66832 KB Output isn't correct
34 Halted 0 ms 0 KB -