Submission #468393

#TimeUsernameProblemLanguageResultExecution timeMemory
468393julian33Horses (IOI15_horses)C++14
100 / 100
483 ms86568 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) { cerr<<vars<<" = "; string delim=""; (...,(cerr<<delim<<values,delim=", ")); cerr<<"\n"; } #else #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) {} #endif #define pb push_back #define sz(x) (int)(x.size()) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> inline void maxa(T& a,T b){a=max(a,b);} template<typename T> inline void mina(T& a,T b){a=min(a,b);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int mxN=5e5+5; //make sure this is right const int mod=1e9+7; #define double long double ll fpow(ll b,ll e){ ll res=1; while(e){ if(e&1) res=(res*b)%mod; b=(b*b)%mod; e>>=1; } return res; } ll divmod(ll a,ll b){ return (a*fpow(b,mod-2))%mod; } ll st[4*mxN],lazy[4*mxN],x[mxN],y[mxN],n,psa2[mxN]; double st2[4*mxN],lazy2[4*mxN],psa[mxN]; void mul(ll &a,ll b){a=(a*b)%mod;} void build(int v,int l,int r){ if(l==r){ st2[v]=psa[l]+log10(y[l]); st[v]=(psa2[l]*y[l])%mod; } else{ int m=(l+r)>>1; build(v<<1,l,m); build(v<<1|1,m+1,r); st2[v]=max(st2[v<<1],st2[v<<1|1]); } } void push(int v){ mul(st[v<<1],lazy[v]); mul(st[v<<1|1],lazy[v]); mul(lazy[v<<1],lazy[v]); mul(lazy[v<<1|1],lazy[v]); lazy[v]=1; st2[v<<1]+=lazy2[v]; st2[v<<1|1]+=lazy2[v]; lazy2[v<<1]+=lazy2[v]; lazy2[v<<1|1]+=lazy2[v]; lazy2[v]=0; } void range_upd(int v,int l,int r,int lq,int rq,ll v1,double v2){ if(lq>rq) return; if(l>=lq && r<=rq){ st[v]=(st[v]*v1)%mod; st2[v]+=v2; lazy2[v]+=v2; lazy[v]=(lazy[v]*v1)%mod; } else{ int m=(l+r)>>1; push(v); range_upd(v<<1,l,m,lq,min(rq,m),v1,v2); range_upd(v<<1|1,m+1,r,max(lq,m+1),rq,v1,v2); st2[v]=max(st2[v<<1],st2[v<<1|1]); } } void point_upd(int v,int l,int r,int ind,ll v1,double v2){ if(l>ind || r<ind) return; if(l==r){ mul(st[v],v1); st2[v]+=v2; } else{ int m=(l+r)>>1; push(v); point_upd(v<<1,l,m,ind,v1,v2); point_upd(v<<1|1,m+1,r,ind,v1,v2); st2[v]=max(st2[v<<1],st2[v<<1|1]); } } int get(int v,int l,int r){ deb(l,r,st[v]); if(l==r) return st[v]; push(v); int m=(l+r)>>1; if(st2[v<<1]>st2[v<<1|1]) return get(v<<1,l,m); return get(v<<1|1,m+1,r); } int init(int N, int X[], int Y[]){ n=N; psa2[0]=1; for(int i=1;i<=n;i++){ x[i]=X[i-1]; y[i]=Y[i-1]; psa[i]=psa[i-1]+log10(x[i]); psa2[i]=(psa2[i-1]*x[i])%mod; } fill(lazy+1,lazy+1+4*n,1); build(1,1,n); return get(1,1,n); } int updateX(int pos, int val){ pos++; ll v=divmod(val,x[pos]); double v2=log10(val)-log10(x[pos]); x[pos]=val; range_upd(1,1,n,pos,n,v,v2); return get(1,1,n); } int updateY(int pos,int val){ pos++; ll v=divmod(val,y[pos]); double v2=log10(val)-log10(y[pos]); y[pos]=val; point_upd(1,1,n,pos,v,v2); return get(1,1,n); }

Compilation message (stderr)

horses.cpp: In function 'int get(int, int, int)':
horses.cpp:114:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  114 |         return st[v];
      |                ~~~~^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:132:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  132 |     build(1,1,n);
      |               ^
horses.cpp:133:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  133 |     return get(1,1,n);
      |                    ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:141:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  141 |     range_upd(1,1,n,pos,n,v,v2);
      |                   ^
horses.cpp:141:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  141 |     range_upd(1,1,n,pos,n,v,v2);
      |                         ^
horses.cpp:142:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  142 |     return get(1,1,n);
      |                    ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:150:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  150 |     point_upd(1,1,n,pos,v,v2);
      |                   ^
horses.cpp:151:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  151 |     return get(1,1,n);
      |                    ^
horses.cpp: In instantiation of 'void logger(std::string, Args&& ...) [with Args = {int&, int&, long long int&}; std::string = std::__cxx11::basic_string<char>]':
horses.cpp:112:5:   required from here
horses.cpp:17:20: warning: unused parameter 'vars' [-Wunused-parameter]
   17 | void logger(string vars, Args&&... values) {}
      |             ~~~~~~~^~~~
horses.cpp:17:32: warning: unused parameter 'values#0' [-Wunused-parameter]
   17 | void logger(string vars, Args&&... values) {}
      |                          ~~~~~~^~~~~~~~~~
horses.cpp:17:32: warning: unused parameter 'values#1' [-Wunused-parameter]
horses.cpp:17:32: warning: unused parameter 'values#2' [-Wunused-parameter]
#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...