| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1107621 |
2024-11-01T18:05:59 Z |
Aviansh |
Horses (IOI15_horses) |
C++17 |
|
1 ms |
336 KB |
#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
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)));
| ~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
