Submission #717218

#TimeUsernameProblemLanguageResultExecution timeMemory
717218dsyzHorses (IOI15_horses)C++17
17 / 100
1334 ms193844 KiB
#include <bits/stdc++.h> #include "horses.h" using namespace std; using ll = long long; using ld = long double; #define MAXN (500005) ll N; ll mod = 1e9 + 7; int x[MAXN], y[MAXN]; struct node{ ll s,e,m; ld lazyadd; pair<ld,ll> v; node *l,*r; node(ll _s,ll _e){ s = _s; e = _e; m = (s + e) / 2; v = {0,s}; lazyadd = 0; if(s != e){ l = new node(s,m); r = new node(m + 1,e); } } pair<ld,ll> value(){ if(s == e){ v.first += lazyadd; lazyadd = 0; return v; } v.first += lazyadd; r -> lazyadd += lazyadd; l -> lazyadd += lazyadd; lazyadd = 0; return v; } void update(ll x,ll y,ld val){ if(s == x && e == y) lazyadd += val; else{ if(x > m) r -> update(x,y,val); else if(y <= m) l -> update(x,y,val); else l -> update(x,m,val), r -> update(m + 1,y,val); v = max(l->value(),r->value()); } } pair<ld,ll> rmq(ll x,ll y){ value(); if(s == x && e == y) return value(); else if(x > m) return r -> rmq(x,y); else if(y <= m) return l -> rmq(x,y); else return max(l -> rmq(x,m),r -> rmq(m + 1,y)); } } *root1; struct node2{ ll s, e, m, val, lazy; node2 *l, *r; node2(ll S, ll E){ s = S, e = E, m = (s+e)/2; val = 0; lazy = 0; if(s != e){ l = new node2(s,m); r = new node2(m + 1,e); } } void propogate(){ if(lazy==0) return; val += lazy*(e-s+1); val %= mod; if(s != e){ //not a leaf, send lazy tags to children (remember to write this if statement) l->lazy += lazy; l->lazy %= mod; r->lazy += lazy; r->lazy %= mod; } lazy = 0; } void update(int S, int E, ll V){ if(s == S && e == E) lazy += V, lazy %= mod; else{ if(E <= m) l->update(S, E, V); else if (m < S) r->update(S, E, V); else l->update(S, m, V),r->update(m+1, E, V); l->propogate(),r->propogate(); val = (l->val + r->val) % mod; } } ll query(int S, int E){ propogate(); //remember to propogate if(s == S && e == E) return val; else if(E <= m) return l->query(S, E); else if(S >= m+1) return r->query(S, E); else return (l->query(S, m) + r->query(m+1, E)) % mod; } } *root2; int init(int n, int X[], int Y[]) { N = n; for(ll i = 0;i < N;i++){ x[i] = X[i]; y[i] = Y[i]; } root1 = new node(0,N + 5); root2 = new node2(0,N + 5); ld logXprefix = 0; for(ll i = 0;i < N;i++){ logXprefix += log(x[i]); root1 -> update(i,i,logXprefix + log(y[i])); } ll prefixX = 1; for(ll i = 0;i < N;i++){ prefixX *= x[i]; prefixX %= mod; root2 -> update(i,i,prefixX); } pair<ld,ll> best = root1 -> rmq(0,N - 1); ll index = best.second; return (root2 -> query(index,index) * y[index]) % mod; } int updateX(int pos, int val) { //pos is 0-indexed root1 -> update(pos,N - 1,-1 * log(x[pos])); ll front = root2 -> query(pos,pos); root2 -> update(pos,N - 1,-1 * front + mod); ll oldx = x[pos]; x[pos] = val; root1 -> update(pos,N - 1,log(x[pos])); ll add = (((front - oldx) % mod) + mod) % mod; root2 -> update(pos,N - 1,add); pair<ld,ll> best = root1 -> rmq(0,N - 1); ll index = best.second; return (root2 -> query(index,index) * y[index]) % mod; } int updateY(int pos, int val) { root1 -> update(pos,pos,-1 * log(y[pos])); y[pos] = val; root1 -> update(pos,pos,log(y[pos])); pair<ld,ll> best = root1 -> rmq(0,N - 1); ll index = best.second; return (root2 -> query(index,index) * y[index]) % mod; }

Compilation message (stderr)

horses.cpp: In member function 'void node::update(ll, ll, ld)':
horses.cpp:38:22: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   38 |  void update(ll x,ll y,ld val){
      |                   ~~~^
horses.cpp:9:14: note: shadowed declaration is here
    9 | int x[MAXN], y[MAXN];
      |              ^
horses.cpp:38:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   38 |  void update(ll x,ll y,ld val){
      |              ~~~^
horses.cpp:9:5: note: shadowed declaration is here
    9 | int x[MAXN], y[MAXN];
      |     ^
horses.cpp: In member function 'std::pair<long double, long long int> node::rmq(ll, ll)':
horses.cpp:47:26: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   47 |  pair<ld,ll> rmq(ll x,ll y){
      |                       ~~~^
horses.cpp:9:14: note: shadowed declaration is here
    9 | int x[MAXN], y[MAXN];
      |              ^
horses.cpp:47:21: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   47 |  pair<ld,ll> rmq(ll x,ll y){
      |                  ~~~^
horses.cpp:9:5: note: shadowed declaration is here
    9 | int x[MAXN], y[MAXN];
      |     ^
horses.cpp: In member function 'void node2::update(int, int, ll)':
horses.cpp:84:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   84 |    else l->update(S, m, V),r->update(m+1, E, V);
      |                      ^
horses.cpp:84:39: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   84 |    else l->update(S, m, V),r->update(m+1, E, V);
      |                                      ~^~
horses.cpp: In member function 'll node2::query(int, int)':
horses.cpp:94:28: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   94 |   else return (l->query(S, m) + r->query(m+1, E)) % mod;
      |                            ^
horses.cpp:94:43: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   94 |   else return (l->query(S, m) + r->query(m+1, E)) % mod;
      |                                          ~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:114:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  114 |   root2 -> update(i,i,prefixX);
      |                   ^
horses.cpp:114:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  114 |   root2 -> update(i,i,prefixX);
      |                     ^
horses.cpp:118:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  118 |  return (root2 -> query(index,index) * y[index]) % mod;
      |                         ^~~~~
horses.cpp:118:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  118 |  return (root2 -> query(index,index) * y[index]) % mod;
      |                               ^~~~~
horses.cpp:118:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  118 |  return (root2 -> query(index,index) * y[index]) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:124:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  124 |  root2 -> update(pos,N - 1,-1 * front + mod);
      |                      ~~^~~
horses.cpp:129:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  129 |  root2 -> update(pos,N - 1,add);
      |                      ~~^~~
horses.cpp:132:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  132 |  return (root2 -> query(index,index) * y[index]) % mod;
      |                         ^~~~~
horses.cpp:132:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  132 |  return (root2 -> query(index,index) * y[index]) % mod;
      |                               ^~~~~
horses.cpp:132:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  132 |  return (root2 -> query(index,index) * y[index]) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:141:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  141 |  return (root2 -> query(index,index) * y[index]) % mod;
      |                         ^~~~~
horses.cpp:141:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  141 |  return (root2 -> query(index,index) * y[index]) % mod;
      |                               ^~~~~
horses.cpp:141:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  141 |  return (root2 -> query(index,index) * y[index]) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
#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...