Submission #1107629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107629		Aviansh	Horses (IOI15_horses)	C++17	54 / 100	85 ms	25928 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

int n;
int *x;
int *y;
int mod = 1e9+7;

template <class T> class segTree{
    private:
        int n;
        T *st;
    public:
        void realMakeST(int *arr, int l, int r, int ind){
            if(l==r){
                st[ind]=arr[l];
            }
            else{
                int mid = (l+r)/2;
                realMakeST(arr,l,mid,ind*2+1);
                realMakeST(arr,mid+1,r,ind*2+2);
                st[ind]=st[ind*2+1]*st[ind*2+2];
                st[ind]%=mod;
            }
        }
        segTree(){
            //aise hi
        }
        segTree(int *arr, int siz){
            int x = (int)pow(2,ceil(log2(siz)));
            n=siz-1;
            x*=2;
            st=new T[x];
            realMakeST(arr,0,n,0);
        }
        void realUpdate(int l, int r, int ind, int pos, int val){
            if(pos<l||pos>r){
                return;
            }
            if(l==r){
                st[ind]=val;
                return;
            }
            int mid = (l+r)/2;
            realUpdate(l,mid,2*ind+1,pos,val);
            realUpdate(mid+1,r,2*ind+2,pos,val);
            st[ind]=st[ind*2+1]*st[ind*2+2];
            st[ind]%=mod;
        }
        void update(int ind, int val){
            realUpdate(0,n,0,ind,val);
        }

        T realQuery(int l, int r, int s, int e, int ind){
            if(e<l||s>r){
                return 1;
            }
            if(s<=l&&r<=e){
                return st[ind];
            }
            int mid = (l+r)/2;
            return (realQuery(l,mid,s,e,2*ind+1)*realQuery(mid+1,r,s,e,2*ind+2))%mod;
        }

        T query(int s,int e){
            return realQuery(0,n,s,e,0);
        }
};
int t = 1;
int *temp = &t;

segTree<long long> st(temp,1);

int finans(){
    if(n<=1000){
        int mx = 0;
        long long curr = 1;
        for(int i = 0;i<n;i++){
            curr*=x[i];
            if(curr>y[mx]){
                mx=i;
                curr=1;
                continue;
            }
            else if(curr*y[i]>y[mx]){
                mx=i;
                curr=1;
                continue;
            }
        }
        long long ans = 1;
        for(int i = 0;i<=mx;i++){
            ans*=x[i];
            ans%=mod;
        }
        ans*=y[mx];
        ans%=mod;
        return ans;
    }
    int mx = max(n-50,0);
    long long curr = 1;
    for(int i = max(n-50,0);i<n;i++){
        curr*=x[i];
        if(curr>y[mx]){
            curr=1;
            mx=i;
        }
        else if(curr*y[i]>y[mx]){
            mx=i;
            curr=1;
        }
    }
    return (st.query(0,mx)*y[mx])%mod;
}

int init(int N, int X[], int Y[]) {
    x=X;
    y=Y;
    n=N;
    st = segTree<long long>(x,n);
    return finans();
}

int updateX(int pos, int val) {
    x[pos]=val;
    st.update(pos,val);
	return finans();
}

int updateY(int pos, int val) {
    y[pos]=val;
	return finans();
}

Compilation message (stderr)

horses.cpp: In constructor 'segTree<T>::segTree(int*, int)':
horses.cpp:31:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   31 |             int x = (int)pow(2,ceil(log2(siz)));
      |                 ^
horses.cpp:6:6: note: shadowed declaration is here
    6 | int *x;
      |      ^
horses.cpp: In function 'int finans()':
horses.cpp:99:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |         return ans;
      |                ^~~
horses.cpp:114:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  114 |     return (st.query(0,mx)*y[mx])%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~^~~~

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