Submission #1005321

#TimeUsernameProblemLanguageResultExecution timeMemory
1005321vjudge1Horses (IOI15_horses)C++17
100 / 100
1166 ms122476 KiB
#pragma GCC optimize("Ofast") #include "bits/stdc++.h" #include "horses.h" #define ld long double #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) { i64 res = 1; while (b) { if (b & 1) res = (res * x) % md; x = (x * x) % md; b >>= 1; } return res; } 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] + log10l(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] + log10l(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, log10l(val), log10l(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, log10l(val), log10l(b[pos])); b[pos] = val; relax2(1, 1, n); i64 ix = st2[1].second; return query1(1, n, ix, 1); }

Compilation message (stderr)

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:58:65: warning: declaration of 'd' shadows a global declaration [-Wshadow]
   58 | 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:73:57: warning: declaration of 'd' shadows a global declaration [-Wshadow]
   73 | 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, long double, long double)':
horses.cpp:134:63: warning: declaration of 'd' shadows a global declaration [-Wshadow]
  134 | 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, long double, long double)':
horses.cpp:149:55: warning: declaration of 'd' shadows a global declaration [-Wshadow]
  149 | 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:180:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  180 |     return query1(1, n, ix, 1);
      |            ~~~~~~^~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:191:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  191 |     return query1(1, n, ix, 1);
      |            ~~~~~~^~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:202:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  202 |     return query1(1, n, ix, 1);
      |            ~~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...