Submission #468391

#	Time	Username	Problem	Language	Result	Execution time	Memory
468391		julian33	Horses (IOI15_horses)	C++14	54 / 100	309 ms	73884 KiB

horses

#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;

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:112:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  112 |         return st[v];
      |                ~~~~^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:130:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  130 |     build(1,1,n);
      |               ^
horses.cpp:131:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  131 |     return get(1,1,n);
      |                    ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:139:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  139 |     range_upd(1,1,n,pos,n,v,v2);
      |                   ^
horses.cpp:139:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  139 |     range_upd(1,1,n,pos,n,v,v2);
      |                         ^
horses.cpp:140:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  140 |     return get(1,1,n);
      |                    ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:148:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  148 |     point_upd(1,1,n,pos,v,v2);
      |                   ^
horses.cpp:149:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  149 |     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:110: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]

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23