Submission #988999

#	Time	Username	Problem	Language	Result	Execution time	Memory
988999		tosivanmak	Horses (IOI15_horses)	C++17	100 / 100	843 ms	88364 KiB

horses

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const __int128 MOD=1e9+7;

 
// TODO: global variables can be declared here
struct SEG{
    vector<ll>seg,arr;
    void init(ll n){
        seg.resize(4*n+5),arr.resize(n+5);
    }
    void build(ll l, ll r, ll id){
        if(l==r){
            seg[id]=arr[l];
        }
        else{
            ll mid=(l+r)>>1;
            build(l,mid,id*2),build(mid+1,r,id*2+1);
            seg[id]=max(seg[id*2],seg[id*2+1]);
        }
    }
    void upd(ll ul, ll l, ll r, ll val, ll id){
        if(l==r){
            seg[id]=val;
        }
        else{
            ll mid=(l+r)>>1;
            if(ul<=mid)upd(ul,l,mid,val,id*2);
            else upd(ul,mid+1,r,val,id*2+1);
            seg[id]=max(seg[id*2],seg[id*2+1]);
        }
    }
    ll qry(ll ql, ll qr, ll l, ll r, ll id){
        if(l>qr||r<ql){
            return -1e18;
        }
        if(l>=ql&&r<=qr)return seg[id];
        ll mid=(l+r)>>1;
        return max(qry(ql,qr,l,mid,id*2),qry(ql,qr,mid+1,r,id*2+1));
    }
}st;
struct MULTIPLICATION{
    vector<ll>seg,arr;
    void init(ll n){
        seg.resize(4*n+5),arr.resize(n+5);
    }
    void build(ll l, ll r, ll id){
        if(l==r){
            seg[id]=arr[l]%MOD;
        }
        else{
            ll mid=(l+r)>>1;
            build(l,mid,id*2),build(mid+1,r,id*2+1);
            seg[id]=seg[id*2]*seg[id*2+1];
            seg[id]%=MOD;
        }
    }
    void upd(ll ul, ll l, ll r, ll val, ll id){
        if(l==r){
            seg[id]=val;
            seg[id]%=MOD;
        }
        else{
            ll mid=(l+r)>>1;
            if(ul<=mid)upd(ul,l,mid,val,id*2);
            else upd(ul,mid+1,r,val,id*2+1);
            seg[id]=seg[id*2]*seg[id*2+1];
            seg[id]%=MOD;
        }
    }
    ll qry(ll ql, ll qr, ll l, ll r, ll id){
        if(l>qr||r<ql){
            return 1;
        }
        if(l>=ql&&r<=qr)return seg[id];
        ll mid=(l+r)>>1;
        return (qry(ql,qr,l,mid,id*2)*qry(ql,qr,mid+1,r,id*2+1)%MOD);
    }
}mul;
vector<ll>qry;
set<ll>ms;
vector<ll>x,y;
ll n;
 
 
ll func(){
    __int128 m=1;
    for(ll u: ms){
        if(m>MOD){break;}
        m*=x[-u];
            qry.push_back(-u);
    }
    ll ans; __int128 maxi=-1e18;
    bool ok=0;
    if(m<=MOD){
        ans=st.qry(1,n,1,n,1);
       ok=1;
    }
    reverse(qry.begin(),qry.end());
    m=1;
    for(int i=0;i<qry.size();i++){
        m*=x[qry[i]];
        __int128 mu;
        if(i==qry.size()-1)mu=st.qry(qry[i],n,1,n,1);
        else mu=st.qry(qry[i],qry[i+1]-1,1,n,1);
        if(mu*m>maxi){
            maxi=mu*m;
            ll store=mu%MOD;
            if(!ok){
                ans=mul.qry(1,qry[i],1,n,1)*store%MOD;
            }
            else{
                ans=max(ans,mul.qry(1,qry[i],1,n,1)*store);
            }
        }
    }
    qry.clear();
    return ans%MOD;
}
int init(int N, int X[], int Y[]) {
  // TODO: implementation
  n=N;
    st.init(N);mul.init(n);
    x.push_back(0),y.push_back(0);
    for(int i=0;i<n;i++){
        x.push_back(X[i]);
        y.push_back(Y[i]);
    }
    for(int i=1;i<=n;i++){
        st.arr[i]=y[i];
        mul.arr[i]=x[i];
    }
    st.build(1,n,1),mul.build(1,n,1);
    for(int i=1;i<=n;i++){
        if(x[i]!=1){
            ms.insert(-i);
        }
    }
    return func();
}
 
int updateX(int pos, int val) {
  // TODO: implementation
  pos++;
  if(x[pos]!=1){
      ms.erase(-pos);
  }
  x[pos]=val;
  mul.upd(pos,1,n,val,1);
  if(x[pos]!=1)ms.insert(-pos);
  return func();
}
 
int updateY(int pos, int val) {
  // TODO: implementation
  pos++;
    y[pos]=val;
  st.upd(pos,1,n,val,1);
  return func();
}

Compilation message (stderr)

horses.cpp: In function 'long long int func()':
horses.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=0;i<qry.size();i++){
      |                 ~^~~~~~~~~~~
horses.cpp:105:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         if(i==qry.size()-1)mu=st.qry(qry[i],n,1,n,1);
      |            ~^~~~~~~~~~~~~~
horses.cpp:109:24: warning: conversion from '__int128' to 'long long int' may change value [-Wconversion]
  109 |             ll store=mu%MOD;
      |                      ~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:140:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  140 |     return func();
      |            ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:152:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  152 |   return func();
      |          ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:160:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  160 |   return func();
      |          ~~~~^~
horses.cpp: In function 'long long int func()':
horses.cpp:94:8: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |     ll ans; __int128 maxi=-1e18;
      |        ^~~

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