Submission #624679

#	Time	Username	Problem	Language	Result	Execution time	Memory
624679		NicolaAbusaad2014	Horses (IOI15_horses)	C++14	100 / 100	929 ms	139872 KiB

horses

#include "horses.h"
    #include <bits/stdc++.h>
     
    using namespace std;
    #define REP(i,l,r) for(long long i=(l);i<(r);i++)
    #define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)
    const long long mod=1e9+7;
    long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;}
    long long squared(long long x){return (x*x)%mod;}
    long long power(long long x,long long p){if(p==0){return 1;}if(p%2==1){return (power(x,p-1)*x)%mod;}return squared(power(x,p/2));}
    long long inv(long long x){return power(x,mod-2);}
    struct segment_tree
    {
        struct node
        {
            long double value;
            long pos,left,right;
        };
        node dum;
        vector<node>tree;
        vector<long double>upd;
        node operation(node x,node z)
        {
            node ret;
            if(x.value>=z.value){
                ret.value=x.value;
                ret.pos=x.pos;
            }
            else{
                ret.value=z.value;
                ret.pos=z.pos;
            }
            ret.left=min(x.left,z.left);
            ret.right=max(x.right,z.right);
            return ret;
        }
        void push(long node)
        {
            tree[node].value+=upd[node];
            if(node<tree.size()/2){
                upd[node*2]+=upd[node];
                upd[(node*2)+1]+=upd[node];
            }
            upd[node]=0;
        }
        void build(vector<long double>v)
        {
            tree.clear();
            upd.clear();
            int x=((v.size())*2)-1;
            while(x&(x-1)){
                x=x&(x-1);
            }
            tree.resize(x*2);
            upd.resize(x*2);
            dum.value=-1e9;
            dum.left=-1e9;
            dum.right=1e9;
            for(long i=0;i<v.size();i++){
                tree[i+x].value=v[i];
                tree[i+x].pos=i;
                tree[i+x].left=i;
                tree[i+x].right=i;
            }
            for(long i=v.size();i<x;i++){
                tree[i+x].value=-1e9;
                tree[i+x].pos=i;
                tree[i+x].left=i;
                tree[i+x].right=i;
            }
            for(long i=x-1;i>0;i--){
                tree[i]=operation(tree[i*2],tree[(i*2)+1]);
            }
        }
        node get(int l,int r,int node=1)
        {
            push(node);
            if(tree[node].left>r||tree[node].right<l){
                return dum;
            }
            if(tree[node].left>=l&&tree[node].right<=r){
                return tree[node];
            }
            return operation(get(l,r,node*2),get(l,r,(node*2)+1));
        }
        void update(int l,int r,long double z,int node=1)
        {
            push(node);
            if(tree[node].left>r||tree[node].right<l){
                return;
            }
            if(tree[node].left>=l&&tree[node].right<=r){
                upd[node]+=z;
                push(node);
                return;
            }
            update(l,r,z,node*2);
            update(l,r,z,(node*2)+1);
            tree[node]=operation(tree[node*2],tree[(node*2)+1]);
        }
    };
    struct segment_tree_mul
    {
        struct node
        {
            long long value,left,right;
        };
        node dum;
        vector<node>tree;
        vector<long long>upd;
        node operation(node x,node z)
        {
            node ret;
            ret.value=(x.value*z.value)%mod;
            ret.left=min(x.left,z.left);
            ret.right=max(x.right,z.right);
            return ret;
        }
        void push(long node)
        {
            if(upd[node]!=1){
                tree[node].value*=power(upd[node],tree[node].right-tree[node].left+1);
                tree[node].value%=mod;
                if(node<tree[0].value){
                    upd[node*2]*=upd[node];
                    upd[node*2]%=mod;
                    upd[(node*2)+1]*=upd[node];
                    upd[(node*2)+1]%=mod;
                }
                upd[node]=1;
            }
        }
        void build(vector<long long>v)
        {
            tree.clear();
            upd.clear();
            long long x=((v.size())*2)-1;
            while(x&(x-1)){
                x=x&(x-1);
            }
            tree.resize(x*2);
            upd.resize(x*2);
            tree[0].value=x;
            dum.value=1;
            dum.left=-1e18;
            dum.right=1e18;
            for(long i=0;i<v.size();i++){
                upd[i+x]=1;
                tree[i+x].value=v[i];
                tree[i+x].left=i;
                tree[i+x].right=i;
            }
            for(long i=v.size();i<x;i++){
                upd[i+x]=1;
                tree[i+x].value=1;
                tree[i+x].left=i;
                tree[i+x].right=i;
            }
            for(long i=x-1;i>0;i--){
                upd[i]=1;
                tree[i]=operation(tree[i*2],tree[(i*2)+1]);
            }
        }
        node get(long long l,long long r,long node=1)
        {
            push(node);
            if(tree[node].left>r||tree[node].right<l){
                return dum;
            }
            if(tree[node].left>=l&&tree[node].right<=r){
                return tree[node];
            }
            return operation(get(l,r,node*2),get(l,r,(node*2)+1));
        }
        void update(long long l,long long r,long long z,long long node=1)
        {
            push(node);
            if(tree[node].left>r||tree[node].right<l){
                return;
            }
            if(tree[node].left>=l&&tree[node].right<=r){
                upd[node]*=z;
                upd[node]%=mod;
                push(node);
                return;
            }
            update(l,r,z,node*2);
            update(l,r,z,(node*2)+1);
            tree[node]=operation(tree[node*2],tree[(node*2)+1]);
        }
    };
    segment_tree st;
    segment_tree_mul ans;
    long n;
    vector<long long>x,y,tot;
    vector<long double>v;
    int init(int N, int X[], int Y[]) {
        n=N;
        x.resize(n);
        y.resize(n);
        tot.resize(n);
        v.resize(n);
        REP(i,0,n){
            x[i]=X[i];
            y[i]=Y[i];
        }
        v[0]=log(x[0])+log(y[0]);
        tot[0]=x[0];
        REP(i,1,n){
            v[i]=v[i-1]+log(x[i])+log(y[i])-log(y[i-1]);
            tot[i]=(tot[i-1]*x[i])%mod;
        }
        st.build(v);
        ans.build(tot);
        N=st.get(0,n-1).pos;
        return (tot[N]*y[N])%mod;
    }
     
    int updateX(int pos, int val) {
    	long long V=val;
    	st.update(pos,n-1,log(V)-log(x[pos]));
    	ans.update(pos,n-1,(V*inv(x[pos]))%mod);
        x[pos]=V;
        V=st.get(0,n-1).pos;
        return (ans.get(V,V).value*y[V])%mod;
    }
     
    int updateY(int pos, int val) {
        long long V=val;
    	st.update(pos,pos,log(V)-log(y[pos]));
        y[pos]=V;
        V=st.get(0,n-1).pos;
        return (ans.get(V,V).value*y[V])%mod;
    }

Compilation message (stderr)

horses.cpp: In member function 'void segment_tree::push(long int)':
horses.cpp:37:24: warning: declaration of 'node' shadows a member of 'segment_tree' [-Wshadow]
   37 |         void push(long node)
      |                   ~~~~~^~~~
horses.cpp:14:16: note: shadowed declaration is here
   14 |         struct node
      |                ^~~~
horses.cpp:40:20: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<segment_tree::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             if(node<tree.size()/2){
      |                ~~~~^~~~~~~~~~~~~~
horses.cpp: In member function 'void segment_tree::build(std::vector<long double>)':
horses.cpp:50:33: warning: conversion from 'std::vector<long double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   50 |             int x=((v.size())*2)-1;
      |                   ~~~~~~~~~~~~~~^~
horses.cpp:59:27: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             for(long i=0;i<v.size();i++){
      |                          ~^~~~~~~~~
horses.cpp: In member function 'segment_tree::node segment_tree::get(int, int, int)':
horses.cpp:75:34: warning: declaration of 'node' shadows a member of 'segment_tree' [-Wshadow]
   75 |         node get(int l,int r,int node=1)
      |                              ~~~~^~~~~~
horses.cpp:14:16: note: shadowed declaration is here
   14 |         struct node
      |                ^~~~
horses.cpp: In member function 'void segment_tree::update(int, int, long double, int)':
horses.cpp:86:51: warning: declaration of 'node' shadows a member of 'segment_tree' [-Wshadow]
   86 |         void update(int l,int r,long double z,int node=1)
      |                                               ~~~~^~~~~~
horses.cpp:14:16: note: shadowed declaration is here
   14 |         struct node
      |                ^~~~
horses.cpp: In member function 'void segment_tree_mul::push(long int)':
horses.cpp:119:24: warning: declaration of 'node' shadows a member of 'segment_tree_mul' [-Wshadow]
  119 |         void push(long node)
      |                   ~~~~~^~~~
horses.cpp:104:16: note: shadowed declaration is here
  104 |         struct node
      |                ^~~~
horses.cpp: In member function 'void segment_tree_mul::build(std::vector<long long int>)':
horses.cpp:147:27: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |             for(long i=0;i<v.size();i++){
      |                          ~^~~~~~~~~
horses.cpp: In member function 'segment_tree_mul::node segment_tree_mul::get(long long int, long long int, long int)':
horses.cpp:164:47: warning: declaration of 'node' shadows a member of 'segment_tree_mul' [-Wshadow]
  164 |         node get(long long l,long long r,long node=1)
      |                                          ~~~~~^~~~~~
horses.cpp:104:16: note: shadowed declaration is here
  104 |         struct node
      |                ^~~~
horses.cpp: In member function 'void segment_tree_mul::update(long long int, long long int, long long int, long long int)':
horses.cpp:175:67: warning: declaration of 'node' shadows a member of 'segment_tree_mul' [-Wshadow]
  175 |         void update(long long l,long long r,long long z,long long node=1)
      |                                                         ~~~~~~~~~~^~~~~~
horses.cpp:104:16: note: shadowed declaration is here
  104 |         struct node
      |                ^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:215:21: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  215 |         N=st.get(0,n-1).pos;
      |                    ~^~
horses.cpp:215:25: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  215 |         N=st.get(0,n-1).pos;
      |           ~~~~~~~~~~~~~~^~~
horses.cpp:216:29: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  216 |         return (tot[N]*y[N])%mod;
      |                ~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:221:21: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  221 |      st.update(pos,n-1,log(V)-log(x[pos]));
      |                    ~^~
horses.cpp:224:21: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  224 |         V=st.get(0,n-1).pos;
      |                    ~^~
horses.cpp:225:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  225 |         return (ans.get(V,V).value*y[V])%mod;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:232:21: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  232 |         V=st.get(0,n-1).pos;
      |                    ~^~
horses.cpp:233:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  233 |         return (ans.get(V,V).value*y[V])%mod;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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