Submission #705344

#	Time	Username	Problem	Language	Result	Execution time	Memory
705344		bin9638	Horses (IOI15_horses)	C++17	17 / 100	687 ms	34524 KiB

horses

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fs first
#define sc second
#define N 500010
#define pb push_back
#define ii pair<int,int>

const ll mod=1e9+7;

struct IT
{
    ll ST[N*4]={};

    void update(int id,int l,int r,int i,int val)
    {
        if(l>i||r<i)
            return;
        if(l==r)
        {
            ST[id]=val;
            return;
        }
        int mid=(l+r)/2;
        update(id*2,l,mid,i,val);
        update(id*2+1,mid+1,r,i,val);
        ST[id]=max(ST[id*2],ST[id*2+1]);
    }

    ll get(int id,int l,int r,int u,int v)
    {
        if(l>v||r<u)
            return 0;
        if(l>=u&&r<=v)
            return ST[id];
        int mid=(l+r)/2;
        return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
    }
}IT_X,IT_Y;

ll bit[N];
int n;
ll x[N],y[N];

ll mu(ll x,ll y)
{
    x%=mod;
    ll res=1;
    for(;y>0;y>>=1,x=x*x%mod)
        if(y&1)
            res=res*x%mod;
    return res;
}

void updatebit(int u,ll val)
{
    for(;u<=n;u+=u&(-u))
        bit[u]=bit[u]*val%mod;
}

ll getbit(int u)
{
    ll res=1;
    for(;u>0;u-=u&(-u))
        res=res*bit[u]%mod;
    return res;
}

ll solve()
{
    ll res=getbit(n)*y[n]%mod,S=x[n];
    ii ps={y[n],1};
    int vt=n;
    while(vt>1)
    {
        int cc=IT_X.get(1,1,n,1,vt-1);
        //cc->vt-1
        ii p={IT_Y.get(1,1,n,max(cc,1),vt-1),S};
      //  cout<<cc+1<<" "<<vt<<" "<<p.fs<<endl;
        if(p.fs*ps.sc>ps.fs*p.sc)
        {
           // cout<<"cc\n";
            ps=p;
            res=p.fs*getbit(vt-1)%mod;
        }
        S*=x[cc];
        if(S>=2e9)
            break;
        vt=cc;
    }
    return res%mod;
}

ll updateX(int pos, int val)
{
    pos++;
    updatebit(pos,mu(x[pos],mod-2));
    x[pos]=val;
    updatebit(pos,val);
    IT_X.update(1,1,n,pos,pos*(val!=1));
    return solve();
}

ll  updateY(int pos, int val)
{
    pos++;
    y[pos]=val;
    IT_Y.update(1,1,n,pos,val);
    return solve();
}

ll init(int cc,int X[],int Y[])
{
    n=cc;
    //cout<<n<<endl;
    for(int i=1;i<=n;i++)
    {
        x[i]=X[i-1];
        y[i]=Y[i-1];
        bit[i]=1;
       // cout<<x[i]<<" "<<y[i]<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        if(x[i]!=1)
            IT_X.update(1,1,n,i,i);
        IT_Y.update(1,1,n,i,y[i]);
        updatebit(i,x[i]);
    }

    return solve();
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    int n;
    cin>>n;
    int x[n],y[n];
    for(int i=0;i<n;i++)
        cin>>x[i];
    for(int i=0;i<n;i++)
        cin>>y[i];
    cout<<init(n,x,y)<<endl;
    int q;
    cin>>q;
    while(q--)
    {
        int type,pos,val;
        cin>>type>>pos>>val;
        if(type==1)
            cout<<updateX(pos,val)<<endl;
                else cout<<updateY(pos,val)<<endl;
    }
    return 0;
}
#endif // SKY

Compilation message (stderr)

horses.cpp: In function 'long long int mu(long long int, long long int)':
horses.cpp:48:15: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   48 | ll mu(ll x,ll y)
      |               ^
horses.cpp:46:9: note: shadowed declaration is here
   46 | ll x[N],y[N];
      |         ^
horses.cpp:48:10: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   48 | ll mu(ll x,ll y)
      |          ^
horses.cpp:46:4: note: shadowed declaration is here
   46 | ll x[N],y[N];
      |    ^
horses.cpp: In function 'long long int solve()':
horses.cpp:79:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |         int cc=IT_X.get(1,1,n,1,vt-1);
      |                ~~~~~~~~^~~~~~~~~~~~~~
horses.cpp:90:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   90 |         if(S>=2e9)
      |            ^
horses.cpp: In function 'long long int init(int, int*, int*)':
horses.cpp:130:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  130 |         IT_Y.update(1,1,n,i,y[i]);
      |                             ~~~^

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