Submission #1107621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107621		Aviansh	Horses (IOI15_horses)	C++17	0 / 100	1 ms	336 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(int *arr, int siz){
            int x = 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){
            cout << "updating" << endl;
            if(pos<l||pos>r){
                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){ cout << "qin" << endl;
            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);
        }
};

segTree<long long> st(x,5);

int finans(){
    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[]) {
    cout << "hello" << endl;
    x=X;
    y=Y;
    n=N;
    cout << "make segtree" << endl;
    st = segTree<long long>(x,n);
    cout << "made segtree" << endl;
	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:28:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   28 |             int x = 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:81:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |     return (st.query(0,mx)*y[mx])%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In instantiation of 'segTree<T>::segTree(int*, int) [with T = long long int]':
horses.cpp:65:26:   required from here
horses.cpp:28:24: warning: conversion from '__gnu_cxx::__promote_2<int, double, double, double>::__type' {aka 'double'} to 'int' may change value [-Wfloat-conversion]
   28 |             int x = pow(2,ceil(log2(siz)));
      |                     ~~~^~~~~~~~~~~~~~~~~~~

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