oj.uz

Submission #708592

# Submission time Handle Problem Language Result Execution time Memory
708592 2023-03-12T04:08:14 Z cig32 Horses (IOI15_horses) C++17
100 / 100
 669 ms 123444 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 14;
const int MOD = 1e9 + 7;
long long x[MAXN];
long long y[MAXN];
int n;


struct segtr {
  long double ans = 0, lazy = 0;
  bool push = 0;
  int id;
} st[4 * MAXN];

void push_down(int idx) {
  if(st[idx].push) {
    st[2*idx+1].ans += st[idx].lazy;
    st[2*idx+1].lazy += st[idx].lazy;
    st[2*idx+1].push = 1;
    st[2*idx+2].ans += st[idx].lazy;
    st[2*idx+2].lazy += st[idx].lazy;
    st[2*idx+2].push = 1;
    st[idx].push = 0;
    st[idx].lazy = 0;
  }
}

void build(int l, int r, int tar) {
  if(l == r) {
    st[tar].id = l;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, 2*tar + 1);
  build(mid+1, r, 2*tar + 2);
  st[tar].id = st[2*tar+1].id;
}
void u(int l, int r, int constl, int constr, int idx, long double uwu) {

  if(l <= constl && constr <= r) {
    st[idx].ans += uwu;
    st[idx].lazy += uwu;
    st[idx].push = 1;
    return;
  }
  push_down(idx);
  int mid = (constl + constr) >> 1;
  if(mid < l || r < constl) u(l, r, mid + 1, constr, 2 * idx + 2, uwu);
  else if(constr < l || r < mid+1) u(l, r, constl, mid, 2 * idx + 1, uwu);
  else {
    u(l, r, constl, mid, 2 * idx + 1, uwu);
    u(l, r, mid + 1, constr, 2 * idx + 2, uwu);
  }
  st[idx].ans = max(st[2*idx+1].ans, st[2*idx+2].ans);
  if(abs(st[idx].ans - st[2*idx+1].ans) < abs(st[idx].ans - st[2*idx+2].ans)) st[idx].id = st[2*idx+1].id;
  else st[idx].id = st[2*idx+2].id;
}

pair<long double, int> qu(int l, int r, int constl, int constr, int idx) {
  if(l <= constl && constr <= r) return {st[idx].ans, st[idx].id};
  push_down(idx);
  int mid = (constl + constr) >> 1;
  if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
  else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
  else {
    return max(qu(l, r, constl, mid, 2*idx+1), qu(l, r, mid+1, constr, 2*idx+2));
  }
}

long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}

long long bit[MAXN];

// To use

void mul(int x, long long y) {
  x++;
  for(;x<MAXN;x+=x&-x) bit[x] = (bit[x] * y) % MOD;
}
void div(int x, long long y) {
  x++;
  long long invy = inv(y);
  for(;x<MAXN;x+=x&-x) bit[x] = (bit[x] * invy) % MOD;
}
long long prod(int x) {
  x++;
  long long ret = 1;
  for(;x; x-=x&-x) ret = (ret * bit[x]) % MOD;
  return ret;
}

void x_upd(int l, int r, long double v) {
  u(l, r, 0, MAXN - 1, 0, v);
}

long double thelog(int x) {
  return 1000.0 * log2(x);
}

int find_best_index() {
  return qu(0, n - 1, 0, MAXN - 1, 0).second;
}

int eval() {
  int fbi = find_best_index();
  long long ans = (prod(fbi) * y[fbi]) % MOD;
  //cout << fbi << ' ' << prod(fbi) << ' ' << y[fbi] << '\n';
  return (int) ans;
}

int init(int N, int X[], int Y[]) {
  n = N;
  build(0, MAXN - 1, 0);
  for(int i=0; i<n; i++) x[i] = X[i];
  for(int i=0; i<n; i++) y[i] = Y[i];
  for(int i=0; i<=n; i++) bit[i] = 1;
  for(int i=0; i<n; i++) mul(i, x[i]);
  long double thelogsum = 0;
  for(int i=0; i<n; i++) {
    thelogsum += thelog(x[i]);
    long double simp = thelogsum + thelog(y[i]);
    x_upd(i, i, simp);
  }

  return eval();
}

int updateX(int pos, int val) {
  div(pos, x[pos]);
  x_upd(pos, n - 1, thelog(val)-thelog(x[pos]));
  x[pos] = val;
  mul(pos, x[pos]);
  return eval();
}

int updateY(int pos, int val) {
  x_upd(pos, pos, thelog(val)-thelog(y[pos]));
  y[pos] = val;
  return eval();
}

Compilation message

horses.cpp: In function 'void mul(int, long long int)':
horses.cpp:86:27: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   86 | void mul(int x, long long y) {
      |                 ~~~~~~~~~~^
horses.cpp:7:11: note: shadowed declaration is here
    7 | long long y[MAXN];
      |           ^
horses.cpp:86:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   86 | void mul(int x, long long y) {
      |          ~~~~^
horses.cpp:6:11: note: shadowed declaration is here
    6 | long long x[MAXN];
      |           ^
horses.cpp: In function 'void div(int, long long int)':
horses.cpp:90:27: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   90 | void div(int x, long long y) {
      |                 ~~~~~~~~~~^
horses.cpp:7:11: note: shadowed declaration is here
    7 | long long y[MAXN];
      |           ^
horses.cpp:90:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   90 | void div(int x, long long y) {
      |          ~~~~^
horses.cpp:6:11: note: shadowed declaration is here
    6 | long long x[MAXN];
      |           ^
horses.cpp: In function 'long long int prod(int)':
horses.cpp:95:20: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   95 | long long prod(int x) {
      |                ~~~~^
horses.cpp:6:11: note: shadowed declaration is here
    6 | long long x[MAXN];
      |           ^
horses.cpp: In function 'long double thelog(int)':
horses.cpp:106:24: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  106 | long double thelog(int x) {
      |                    ~~~~^
horses.cpp:6:11: note: shadowed declaration is here
    6 | long long x[MAXN];
      |           ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:130:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  130 |     thelogsum += thelog(x[i]);
      |                         ~~~^
horses.cpp:131:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  131 |     long double simp = thelogsum + thelog(y[i]);
      |                                           ~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:140:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  140 |   x_upd(pos, n - 1, thelog(val)-thelog(x[pos]));
      |                                        ~~~~~^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:147:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  147 |   x_upd(pos, pos, thelog(val)-thelog(y[pos]));
      |                                      ~~~~~^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 94284 KB Output is correct
2 Correct 60 ms 94180 KB Output is correct
3 Correct 66 ms 94284 KB Output is correct
4 Correct 61 ms 94240 KB Output is correct
5 Correct 69 ms 94248 KB Output is correct
6 Correct 60 ms 94284 KB Output is correct
7 Correct 69 ms 94268 KB Output is correct
8 Correct 63 ms 94172 KB Output is correct
9 Correct 62 ms 94268 KB Output is correct
10 Correct 61 ms 94208 KB Output is correct
11 Correct 59 ms 94280 KB Output is correct
12 Correct 63 ms 94248 KB Output is correct
13 Correct 61 ms 94296 KB Output is correct
14 Correct 61 ms 94452 KB Output is correct
15 Correct 61 ms 94168 KB Output is correct
16 Correct 61 ms 94284 KB Output is correct
17 Correct 65 ms 94276 KB Output is correct
18 Correct 66 ms 94192 KB Output is correct
19 Correct 63 ms 94284 KB Output is correct
20 Correct 60 ms 94240 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94264 KB Output is correct
2 Correct 62 ms 94228 KB Output is correct
3 Correct 67 ms 94244 KB Output is correct
4 Correct 66 ms 94244 KB Output is correct
5 Correct 64 ms 94184 KB Output is correct
6 Correct 69 ms 94240 KB Output is correct
7 Correct 69 ms 94192 KB Output is correct
8 Correct 70 ms 94232 KB Output is correct
9 Correct 67 ms 94240 KB Output is correct
10 Correct 64 ms 94276 KB Output is correct
11 Correct 64 ms 94284 KB Output is correct
12 Correct 69 ms 94180 KB Output is correct
13 Correct 61 ms 94280 KB Output is correct
14 Correct 64 ms 94204 KB Output is correct
15 Correct 62 ms 94236 KB Output is correct
16 Correct 58 ms 94236 KB Output is correct
17 Correct 59 ms 94264 KB Output is correct
18 Correct 60 ms 94352 KB Output is correct
19 Correct 61 ms 94256 KB Output is correct
20 Correct 63 ms 94260 KB Output is correct
21 Correct 58 ms 94228 KB Output is correct
22 Correct 58 ms 94228 KB Output is correct
23 Correct 61 ms 94256 KB Output is correct
24 Correct 62 ms 94304 KB Output is correct
25 Correct 60 ms 94232 KB Output is correct
26 Correct 63 ms 94284 KB Output is correct
27 Correct 64 ms 94320 KB Output is correct
28 Correct 65 ms 94224 KB Output is correct
29 Correct 64 ms 94304 KB Output is correct
30 Correct 66 ms 94284 KB Output is correct
31 Correct 70 ms 94220 KB Output is correct
32 Correct 65 ms 94336 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 114656 KB Output is correct
2 Correct 612 ms 123360 KB Output is correct
3 Correct 582 ms 114636 KB Output is correct
4 Correct 669 ms 118628 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 94324 KB Output is correct
2 Correct 61 ms 94248 KB Output is correct
3 Correct 64 ms 94248 KB Output is correct
4 Correct 60 ms 94256 KB Output is correct
5 Correct 60 ms 94168 KB Output is correct
6 Correct 61 ms 94212 KB Output is correct
7 Correct 61 ms 94188 KB Output is correct
8 Correct 63 ms 94292 KB Output is correct
9 Correct 64 ms 94280 KB Output is correct
10 Correct 62 ms 94284 KB Output is correct
11 Correct 60 ms 94272 KB Output is correct
12 Correct 64 ms 94288 KB Output is correct
13 Correct 73 ms 94252 KB Output is correct
14 Correct 61 ms 94288 KB Output is correct
15 Correct 61 ms 94284 KB Output is correct
16 Correct 61 ms 94236 KB Output is correct
17 Correct 60 ms 94296 KB Output is correct
18 Correct 60 ms 94236 KB Output is correct
19 Correct 65 ms 94288 KB Output is correct
20 Correct 67 ms 94244 KB Output is correct
21 Correct 60 ms 94260 KB Output is correct
22 Correct 60 ms 94208 KB Output is correct
23 Correct 62 ms 94284 KB Output is correct
24 Correct 64 ms 94328 KB Output is correct
25 Correct 64 ms 94316 KB Output is correct
26 Correct 66 ms 94268 KB Output is correct
27 Correct 66 ms 94332 KB Output is correct
28 Correct 66 ms 94336 KB Output is correct
29 Correct 67 ms 94228 KB Output is correct
30 Correct 66 ms 94268 KB Output is correct
31 Correct 60 ms 94272 KB Output is correct
32 Correct 62 ms 94384 KB Output is correct
33 Correct 365 ms 113796 KB Output is correct
34 Correct 363 ms 113816 KB Output is correct
35 Correct 402 ms 120736 KB Output is correct
36 Correct 398 ms 120808 KB Output is correct
37 Correct 333 ms 111988 KB Output is correct
38 Correct 363 ms 112896 KB Output is correct
39 Correct 330 ms 112044 KB Output is correct
40 Correct 365 ms 115976 KB Output is correct
41 Correct 313 ms 112040 KB Output is correct
42 Correct 347 ms 112204 KB Output is correct
43 Correct 362 ms 116284 KB Output is correct
44 Correct 373 ms 116252 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 94284 KB Output is correct
2 Correct 72 ms 94200 KB Output is correct
3 Correct 71 ms 94260 KB Output is correct
4 Correct 60 ms 94284 KB Output is correct
5 Correct 59 ms 94292 KB Output is correct
6 Correct 62 ms 94336 KB Output is correct
7 Correct 60 ms 94192 KB Output is correct
8 Correct 61 ms 94204 KB Output is correct
9 Correct 67 ms 94224 KB Output is correct
10 Correct 68 ms 94320 KB Output is correct
11 Correct 65 ms 94192 KB Output is correct
12 Correct 61 ms 94292 KB Output is correct
13 Correct 62 ms 94284 KB Output is correct
14 Correct 63 ms 94212 KB Output is correct
15 Correct 66 ms 94188 KB Output is correct
16 Correct 68 ms 94184 KB Output is correct
17 Correct 63 ms 94260 KB Output is correct
18 Correct 59 ms 94368 KB Output is correct
19 Correct 60 ms 94216 KB Output is correct
20 Correct 62 ms 94364 KB Output is correct
21 Correct 65 ms 94292 KB Output is correct
22 Correct 64 ms 94240 KB Output is correct
23 Correct 63 ms 94284 KB Output is correct
24 Correct 64 ms 94272 KB Output is correct
25 Correct 63 ms 94352 KB Output is correct
26 Correct 63 ms 94416 KB Output is correct
27 Correct 62 ms 94252 KB Output is correct
28 Correct 66 ms 94240 KB Output is correct
29 Correct 69 ms 94260 KB Output is correct
30 Correct 63 ms 94228 KB Output is correct
31 Correct 61 ms 94248 KB Output is correct
32 Correct 64 ms 94308 KB Output is correct
33 Correct 479 ms 114608 KB Output is correct
34 Correct 626 ms 123444 KB Output is correct
35 Correct 634 ms 114612 KB Output is correct
36 Correct 639 ms 118452 KB Output is correct
37 Correct 384 ms 113816 KB Output is correct
38 Correct 414 ms 113812 KB Output is correct
39 Correct 468 ms 120744 KB Output is correct
40 Correct 441 ms 120692 KB Output is correct
41 Correct 352 ms 111992 KB Output is correct
42 Correct 426 ms 112904 KB Output is correct
43 Correct 370 ms 111932 KB Output is correct
44 Correct 450 ms 115812 KB Output is correct
45 Correct 368 ms 111924 KB Output is correct
46 Correct 397 ms 111972 KB Output is correct
47 Correct 424 ms 116252 KB Output is correct
48 Correct 426 ms 116256 KB Output is correct
49 Correct 625 ms 115864 KB Output is correct
50 Correct 607 ms 115812 KB Output is correct
51 Correct 525 ms 122672 KB Output is correct
52 Correct 562 ms 122284 KB Output is correct
53 Correct 504 ms 114256 KB Output is correct
54 Correct 534 ms 114800 KB Output is correct
55 Correct 480 ms 112956 KB Output is correct
56 Correct 532 ms 117676 KB Output is correct
57 Correct 406 ms 113692 KB Output is correct
58 Correct 425 ms 114300 KB Output is correct
59 Correct 360 ms 116344 KB Output is correct