Submission #1107762

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1107762	2024-11-02T04:58:44 Z	Aviansh	Horses (IOI15_horses)	C++17	Compilation error	0 ms	0 KB

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);
        }
};
 
 
template <class T> class segTreeMax{
    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;
            }
        }
        segTreeMax(){
            //aise hi
        }
        segTreeMax(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);
segTreeMax<long long> stmax(temp,1);
set<pair<int,int>>ones;
 
int finans(){
    int mx = n-1;
    long long curr = 1;
    int mxy = y[n-1];
    //cout << "here1" << endl;
    set<pair<int,int>>::iterator it = ones.end();
    //cout << "here2" << endl;
    //--it;
    //cout << "ones.size: " << ones.size() << endl;
    bool over = !(ones.size()==0);
    for(int i = n-1;i>=0;i--){
        if(!over&&i==(*it).second){
            i=(*it).first;
            int cury = 0;
            if((*it).second-(*it).first<=15){
                for(int i = (*it).first;i<=(*it).second;i++){
                    cury=max(cury,y[i]);
                }
            }
            else{
                cury = stmax.query((*it).first,(*it).second);
            }
            if(cury>curr){
                mx=i;
                curr=cury;
                mxy=cury;
            }
            if(it==ones.begin()){
                over=1;
            }
            it--;
            if(curr>=1e9){
                break;
            }
            continue;
        }
        if(y[i]>curr){
            mx=i;
            curr=y[i];
            mxy=y[i];
        }
        curr*=x[i];
        if(curr>=1e9){
            break;
        }
    }
    //cout << "returning: " << (1LL*st.query(0,mx)*mxy)%mod << endl;
    return (1LL*st.query(0,mx)*mxy)%mod;
}
 
int init(int N, int X[], int Y[]) {
    x=X;
    y=Y;
    n=N;
    st = segTree<long long>(x,n);
    stmax = segTreeMax<long long>(y,n);
    pair<int,int>rg={-1,-1};
    for(int i = 0;i<n;i++){
        if(x[i]==1){
            if(rg.first==-1){
                rg.first=i;
                rg.second=i;
            }
            else{
                rg.second=i;
            }
        }
        else{
         if(rg.first!=-1)
ones.insert(rg);
            rg={-1,-1};
        }
    }
    if(rg.first!=-1){
        ones.insert(rg);
    }
    int las = -10;
    for(pair<int,int>p:ones){
        assert(p.first-las>1);
        las=p.second;
    }
    //cout << "here" << endl;
    return finans();
}
 
int updateX(int pos, int val) {
    x[pos]=val;
    st.update(pos,val);
	return finans();
}
 
int updateY(int pos, int val) {
    if(y[pos]==1&&val!=1){
        set<pair<int,int>>::iterator it = ones.upper_bound({pos,2e9});
        pair<int,int>p = *(--it);
        ones.erase(p);
        if(p.first!=pos){
            ones.insert({p.first,pos-1});
        }
        if(p.second!=pos){
            ones.insert({pos+1,p.second});
        }
    }
    else if(y[pos]!=1&&val==1){
        if(ones.size()==0){
            ones.insert({pos,pos});
        }
        else{
            set<pair<int,int>>::iterator it = ones.upper_bound({pos,2e9});
            pair<int,int>p={0,0};
            if(it!=ones.begin()){
                p = *(--it);
                if(p.second==pos-1){
                    ones.erase(it);
                    ones.insert({p.first,pos});
                }
                else{
                    ones.insert({pos,pos});
                }
            }
            else{
                ones.insert({pos,pos});
            }
            it=ones.upper_bound({pos,2e9});
            if(it!=ones.end()){
                p=*(it);
                if(p.first==pos+1){
                    pair<int,int>p2=*(--it);
                    ones.erase(it);
                    ones.erase(p2);
                    ones.insert({p2.first,p.second});
                }
            }
        }
    }
    int las = -10;
    for(pair<int,int>p:ones){
        assert(p.first-las>1);
        las=p.second;
    }
    y[pos]=val;
    stmax.update(pos,val);
	return finans();
}

Compilation message

horses.cpp:208:2: error: extended character   is not valid in an identifier
  208 |          if(rg.first!=-1)
      |  ^
horses.cpp:208:5: error: extended character   is not valid in an identifier
  208 |          if(rg.first!=-1)
      |    ^
horses.cpp:208:8: error: extended character   is not valid in an identifier
  208 |          if(rg.first!=-1)
      |      ^
horses.cpp:208:11: error: extended character   is not valid in an identifier
  208 |          if(rg.first!=-1)
      |        ^
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 constructor 'segTreeMax<T>::segTreeMax(int*, int)':
horses.cpp:93:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   93 |             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:155:25: warning: declaration of 'i' shadows a previous local [-Wshadow]
  155 |                 for(int i = (*it).first;i<=(*it).second;i++){
      |                         ^
horses.cpp:150:13: note: shadowed declaration is here
  150 |     for(int i = n-1;i>=0;i--){
      |             ^
horses.cpp:160:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  160 |                 cury = stmax.query((*it).first,(*it).second);
      |                        ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:171:16: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  171 |             if(curr>=1e9){
      |                ^~~~
horses.cpp:182:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  182 |         if(curr>=1e9){
      |            ^~~~
horses.cpp:187:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  187 |     return (1LL*st.query(0,mx)*mxy)%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:208:2: error: '\U000000a0' was not declared in this scope
  208 |          if(rg.first!=-1)
      |  ^